字符串回文

*请定义一个方法用于判断一个字符串是否是对称的字符串,并在主方法中测试方法。例如:“abcba”、**“上海自来水来自海上”*均为对称字符串

思路

  1. 首先观察字符串回文的规律,左右对称

  2. 其次,设想解决方案如下:

    • 反转字符串与当前字符串比较每一个字符
    • 将字符串分成左右两部分进行字符比较
    • 将字符串反转与字符串进行字符比较
  3. 设想实现

    1. 第一个方案,实现使用将字符串转型成字符串工具类进行操作或者转换为数组进行操作
    2. 第二个方案,使用双指针方案,一个从左1向右执行,一个从右1向左执行,直到比较到最中间值
    3. 第三个方案,将字符串正向输出,同时将字符串反向输出的同时进行比较

解题方法

这里采用是第二个方案,使用双指针方案,设置左右哨兵,分别从左1和右1同时向中间查哨比较,比较到最后,最坏的情况就是字符串是奇数,最中间值无法让左右哨兵合理分配比较,有两种处理方式,一让其多比较一次,但是保证不会重复比较,即左右哨兵比较单位相同停止,二,让其不比较最中间值。

Code


class Solution {
     public boolean palindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}