LeetCode——验证回文字符串II

NO.680 验证回文字符串II 简单

思路一：暴力 遍历 s 依次删除每个字符(包含删除空字符，即不删)，判断剩下的新字符串是否为回文串。

时间复杂度：O(n^2) 超时

空间复杂度：O(n) 保存新字符串

思路二：双指针贪心算法 双指针相向遍历，如果 s[i]==s[j] 就 i++;j--; 继续遍历，如果 s[i] != s[j] 则分别删除 i 字符或 j 字符后，剩下的部分子串继续双指针遍历判断是否为回文串，此时可以直接返回判断的结果即可。如果最后走出开始的双指针循环，这说明不需要删除元素，s 本身就是回文串。

public boolean validPalindrome(String s) {
    if (s.equals("")) return true;
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) == s.charAt(j)) {
            i++;
            j--;
        } else {
            //s[i] 和 s[j] 不相等,分别删除 s[i] 或 s[j] 后判断是否为有效回文串
            return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
        }
    }
    return true;
}

//双指针判断 s 的 [i,j] 子串是否为回文串
private boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i) == s.charAt(j)) {
            i++;
            j--;
        } else {
            return false;
        }
    }
    return true;
}

时间复杂度：O(n) 一次遍历

空间复杂度：O(1)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github