018 - 劍指 Offer II 018. 有效的回文【雙指標】

• 時間復雜度： O ( n ) O(n) O(n)
• 空間復雜度： O ( 1 ) O(1) O(1)

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
}

019 - 劍指 Offer II 019. 最多洗掉一個字符得到回文【貪心+雙指標】

設兩個指標從字串兩端向中心靠攏，如果左右指標指向字符相等，則繼續向中心靠攏；如果不相等，則必須洗掉其中一個，那么就產生了兩種情況：洗掉左邊字符、或 洗掉右邊字符，只要以上這兩種情況有一個符合是回文串就回傳 t r u e true true，否則回傳 f a l s e false false，

• 時間復雜度： O ( n ) O(n) O(n)
• 空間復雜度： O ( 1 ) O(1) O(1)

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1); // 洗掉左 || 洗掉右
            }
        }

        return true;
    }
	
    // 判斷字串s是否是回文串
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }

        return true;
    }
}

020 - 劍指 Offer II 020. 回文子字串的個數【動態規劃、中心擴展】

方法一：動態規劃

設定 d p [ i ] [ j ] dp[i][j] dp[i][j]表示字串 s s s在 [ i , j ] [i,j] [i,j]區間的子串是否是一個回文串，

狀態轉移方程：$dp[i][j] = \left{
\begin{aligned}
true, 如果 s[i] == s[j] 并且 (j-i<=1 || dp[i+1][j-1]) \
fasle, 其他
\end{aligned}
\right.
$

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復雜度： O ( n 2 ) O(n^2) O(n2)

class Solution {
    // 動態規劃
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int cnt = 0;

        // 按列計算dp
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

方法二：中心擴展

對于一個子串，選擇最中間的a作為中心點，往兩邊擴展，如果中心串是回文串，并且向兩側擴展的左右兩個字符一樣，則產生了一個新的回文串，依次繼續擴展，

對于“中心點”，可以是一個字符，也可能是兩個字符，這樣中心點的個數就有 2 ? n ? 1 2*n-1 2?n?1個，其中單個字符的中心點有 n n n個，兩個字符的中心點有 n ? 1 n-1 n?1個，

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復雜度： O ( 1 ) O(1) O(1)

class Solution {
    // 中心擴展
    public int countSubstrings(String s) {
        int n = s.length();
        int freq = 2 * n - 1;
        int cnt = 0;

        for (int i = 0; i < freq; i++) {
            int left = i / 2, right = i / 2 + i % 2;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                cnt++;
            }
        }

        return cnt;
    }
}