回文部分文字列のカウント

この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s[j]の場合、必ず回文ではありません。したがって、dp[i][j]をインデックス範囲[i,j]の部分文字列が回文であるかどうかを表すとして定義します。

初期状態ではマッチングを行っていないため、すべてfalseで初期化します。探索順序については、[i+1,j-1]から[i,j]を導出するため、iは大きい方から小さい方へ、jは小さい方から大きい方へと進める必要があります。

class Solution {
public:
    int countSubstrings(const string& str) {
        vector<vector<bool>> isPalindrome(str.size(), vector<bool>(str.size(), false));
        int count = 0;
        for(int i = str.size() - 1; i >= 0; i--) {
            for(int j = i; j < str.size(); j++) {
                if(str[i] == str[j]) {
                    if(j - i <= 1) {
                        isPalindrome[i][j] = true;
                        count++;
                    }
                    else if(isPalindrome[i + 1][j - 1]) {
                        isPalindrome[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }
};

双ポインタアプローチ

中心要素が1つの場合と2つの場合の2つの状況に分けて考えます。各要素を中心として回文の数を累積していきます。

class Solution {
public:
    int countSubstrings(const string& str) {
        int total = 0;
        for(int center = 0; center < str.size(); center++) {
            total += expandAroundCenter(str, center, center);
            total += expandAroundCenter(str, center, center + 1);
        }
        return total;
    }
private:
    int expandAroundCenter(const string& str, int left, int right) {
        int palindromeCount = 0;
        while(left >= 0 && right < str.size() && str[left] == str[right]) {
            left--;
            right++;
            palindromeCount++;
        }
        return palindromeCount;
    }
};

最長回文部分列

この問題では、dp[i][j]をインデックス[i,j]の部分文字列における最長回文部分列の長さとして直接定義できます。

漸化式：s[i] == s[j]の場合、dp[i][j] = dp[i + 1][j - 1] + 2となります。等しくない場合、[i,j]部分文字列の結果は[i+1,j]と[i,j-1]の2つの部分文字列の結果の最大値に依存し、つまりs[i]を考慮した場合とs[j]を考慮した場合の最大値を取ります。

初期化と探索順序は前の問題と同じです。

class Solution {
public:
    int longestPalindromeSubseq(const string& text) {
        vector<vector<int>> maxLength(text.size(), vector<int>(text.size(), 0));
        for(int i = text.size() - 1; i >= 0; i--) {
            for(int j = i; j < text.size(); j++) {
                if(text[i] == text[j]) {
                    if(j - i <= 1) {
                        maxLength[i][j] = j - i + 1;
                    }
                    else {
                        maxLength[i][j] = maxLength[i + 1][j - 1] + 2;
                    }
                }
                else {
                    maxLength[i][j] = max(maxLength[i + 1][j], maxLength[i][j - 1]);
                }
            }
        }
        return maxLength[0][text.size() - 1];
    }
};