Q 1:回文文字列の分割

Given a string s, partition s such that every substring of the partition is a palindrome.Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return
[ 
   ["aa","b"],
   ["a","a","b"]
]

アルゴリズム遡及法

文字列の先頭からスキャンし、str[0..i]が回文文字列

であるように下付きiを見つけた.

str[0..i]を一時結果

に記入する

は次に、残りの文字列str[i+1,end]に対して、i+1>=endが

を終了するまで、前の2つのステップを再帰的に呼び出す.

この時、私たちは結果を見つけた.

遡及を開始する.最初に遡る位置iを例とする.iから右にスキャンする、str[0..j]を1つの返信文字列とする最初の位置jを見つける.次に、前の4つのステップを繰り返す.

文字列「abc」を例に挙げる.

はまずi=0を見つけ、「a」は回文文字列である.

その後、サブストリング「babc」で検索を継続し、次の「b」を見つけ、「a」、「b」、「c」を再帰的に見つける.これで最初の結果を見つけた.["a", "b", "a", "b", "c"]

cは、cを結果から除去する、位置は、下の3の「b」に遡る.「b」から後ろにstr[3..x]が存在するか否かは回文文字列であり、発見はなかった.

は下の2の「a」に遡り、str[2..x]が回文文字列であるかどうかを検索したが、発見されなかった.

は下の1の「b」に遡り続け、str[1..x]が回文文字列であるかどうかを検索し、「bab」を見つけ、結果に記入する.次に、以下の4からスキャンを継続する.次の返信文字列「c」が見つかりました.

次の結果を見つけた[「a」,「bab」,「c」]

は、その後、遡及+再帰を継続する.

インプリメンテーション

class Solution {
public:
    vector> partition(string s) {
        std::vector<:vector> > results;
        std::vector<:string> res;
        dfs(s, 0, res, results);
        return results;
    }
private:
    void dfs(std::string& s, int startIndex,
            std::vector<:string> res,
            std::vector<:vector> >& results)
    {
        if (startIndex >= s.length())
        {
            results.push_back(res);
        }
        for (int i = startIndex; i < s.length(); ++i)
        {
            int l = startIndex;
            int r = i;
            while (l <= r && s[l] == s[r]) ++l, --r;
            if (l >= r)
            {
                res.push_back(s.substr(startIndex, i - startIndex + 1));
                dfs(s, i + 1, res, results);
                res.pop_back();
            }
        }
    }
};

Q 2回文文字列の最小分割数

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",  
Return 1 since the palindrome partitioning 
["aa","b"] could be produced using 1 cut.

アルゴリズムCalculate and maintain 2 DP states:

dp[i][j] , which is whether s[i..j] forms a pal

isPalindrome[i], which is the minCut for s[i..n-1]

Once we comes to a pal[i][j]==true:

if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0;

else: the current cut num (first cut s[i..j] and then cut the rest s[j+1...n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller. d[0] is the answer.

インプリメンテーション

class Solution {

public:
    int minCut(std::string s) {
        int len = s.length();
        int minCut = 0;
        bool isPalindrome[len][len] = {false};
        int dp[len + 1] = {INT32_MAX};                                                                                                                
        dp[len] = -1;
        for (int leftIndex = len - 1; leftIndex >= 0; --leftIndex)
        {
            for (int midIndex = leftIndex; midIndex <= len - 1; ++midIndex)
            {
                if ((midIndex - leftIndex < 2 || isPalindrome[leftIndex + 1][midIndex -1])
                   && s[leftIndex] == s[midIndex])
                {
                    isPalindrome[leftIndex][midIndex] = true;
                    dp[leftIndex] = std::min(dp[midIndex + 1] + 1, dp[leftIndex]);
                }
            }
            std::cout << leftIndex << ": " << dp[leftIndex] << std::endl;
        }
        return dp[0];
    }   
};