回文字符串判断

问题描述:回文字符串指的是一个顺着读和反过来读都一样的字符串,比如"abcba","poop"等,判断一个字符串是否是回文字符串。

这里提供两种解法:

        解法一:同时从字符串头尾开始向中间扫描字符串,如果所有头尾字符都一样,那么这个字符串就是一个回文字符串。

                   采用这种方法,只需要维护头部和尾部两个扫描指针即可,终止条件是尾指针大于等于头指针。

                   算法的时间复杂度为O(n),空间复杂度为O(1)。

       解法二:从字符串中间位置开始,向两边扩展扫描查看两边字符是否相等。

                  算法的时间复杂度为O(n),空间复杂度为O(1)。

       虽然解法一和解法二的时间复杂度和空间复杂度一样,但是在回文串处理的变形问题中,解法一或解法二可以起到意想不到的效果,可以很方便地处理问题。所以两种解法都要掌握。

       当然还存在其他解法,比如利用栈等数据结构,也可以轻易实现,这里不再多说,读者自己可以去思考。

       由于两种解法都比较简单,这里不再给出详细的代码实现。

原文地址:https://www.cnblogs.com/guozhenqiang/p/5427246.html