動的計画法(DP)で計算結果を再利用して計算量を減らす

(2019-12-30)

LeetCodeの5. Longest Palindromic Substringをやってみた。 文字列に含まれる最長の回文を返す問題。

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

最初に書いたコードはこれ。オーダーは部分文字列を網羅するのにO(n^2)*回文かチェックするのにO(n)=O(n^3)で、タイムアウトしてしまう。

cclass Solution {
    bool isPalindromic(string s) {
        for (int i = 0; i < (s.length() / 2) + 1; i++) {
            if (s[i] != s[s.length() - 1 - i]) {
                return false;
            }
        }
        return true;
    }
public:
    string longestPalindrome(string s) {
        string ret = "";
        for (int i = 0; i < s.length(); i++) {
            if (ret.length() >= s.length() - i) {
                break;
            }
            for (int j = s.length(); j >= i+1; j--) {
                if (ret.length() >= j - i) {
                    break;
                }
                string substr = s.substr(i, j - i);
                if (isPalindromic(substr)) {
                    ret = substr;
                    break;
                }
            }
        }
        return ret;
    }
};

動的計画法(DP, Dynamic Programming)は記録した計算結果を、帰納的に求められるより大きな計算で利用するアルゴリズムの総称。 例えば、フィボナッチ数列の項f(x)を求めるのに、f(x-1)f(x-2)の結果を記録しておけばそれらを足すだけで済む。

今回の問題ではある文字列Sが回文なら、その両端に同じ文字cが付いた文字列cScも回文であることを利用し、 中央の文字を決めて、回文である限り範囲を両端に伸ばしていくことで、回文判定が両端の文字の一致だけのO(1)でできるようになった。 これにより全体のオーダーがO(n^2)に改善され、タイムアウトしなくなった。

class Solution {
    bool isPalindromic(string s) {
        return s[0] == s[s.length() - 1];
    }
public:
    string longestPalindrome(string s) {
        string ret = "";
        for (int i = 0; i < s.length(); i++) {
            if (ret.length() >= min(i*2+2, int(s.length()-i)*2+2)) {
                break;
            }
            for (int j = 1; j <= 2; j++) {
                if(i+j > s.length()) {
                    break;
                }
                string substr = s.substr(i, j);
                if (!isPalindromic(substr)) {
                    break;
                }
                for (int k = 0; k <= i; k++) {
                    if (i+j+k > s.length()) {
                        break;
                    }
                    substr = s.substr(i-k, j+k*2);
                    if (!isPalindromic(substr)) {
                        break;
                    }
                    if (ret.length() < substr.length()) {
                        ret = substr;
                    }
                }
            }
        }
        return ret;
    }
};