LeetCode.332. 删除回文子序列

LeetCode.332. 删除回文子序列

难度：easy

模拟+双指针：看哥么的注释

Java：

class Solution {
    public int removePalindromeSub(String s) {
        // 删除的是子序列，即删除的序列中的元素不一定是连续的
        // 因为字符串s中只有两个元素，所以最多只需要两次删除
        // 若s本身就是回文序列，则只需要一次删除
        int len = s.length();
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                // 不是回文串
                return 2;
            }
        }
        // 是回文串
        return 1;
    }
}

复杂度分析：

时间复杂度：O(n)空间复杂度：O(1)