• 欢迎光临~

leetcode-680-easy

开发技术 开发技术 2022-10-28 次浏览

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true
Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Example 3:

Input: s = "abc"
Output: false
Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

思路一:首先想到用删除字符的方式,遍历 [-1, s.length()] 字符位置,判断字符回文成立,结果超时了。

思路二:那就用双指针实现,因为字符串至多删除一个字符,在回文判断遇到不相等,删除字符完全分类只可能出现两种情况

  • left + 1
  • right - 1
    要么删除左边,要么删除右边,删除字符后的字符串一定是回文
public boolean validPalindrome(String s) {
    char[] chars = s.toCharArray();

    int left = 0;
    int right = s.length() - 1;

    while (left < right) {

        if (chars[left] != chars[right]) {
            return isPalindromic(chars, left+1, right) ||
                    isPalindromic(chars, left, right-1);
        }
        left++;
        right--;
    }

    return true;
}

public boolean isPalindromic(char[] chars, int begin, int end) {
    while (begin < end) {
    if (chars[begin++] != chars[end--]) return false;
    }
    return true;
}
程序员灯塔
转载请注明原文链接:leetcode-680-easy
喜欢 (0)