[leetcode/lintcode問題解]有効回文II・Valid Palindrome II

【タイトル説明】
空でない文字列sに、最大1文字を削除できます.それを文字列に変えることができるかどうかを判断します.
オンライン評価アドレス:https://www.lintcode.com/problem/valid-palindrome-ii/?utm_source=sc-bky-zq
【例】
例1:

  : s = "aba"
  : true
  :        

例2:

  : s = "abca"
  : true
  :    'b'   'c'

例3:

  : s = "abc"
  : false
  :                   

【問題解】
二重ポインタアルゴリズム.両端から真ん中まで歩いて、最初のペアの異なる文字を見つけた後、左を削除するか、右を削除します.

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
        
        return isSubPalindrome(s, left + 1, right) || isSubPalindrome(s, left, right - 1);
    }
    
    private boolean isSubPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

【参考答案】
https://www.jiuzhang.com/solution/valid-palindrome-ii/?utm_source=sc-bky-zq