Q1: 回文字符串的分割

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"]
]

算法
回溯法.

• 從字符串開(kāi)頭掃描, 找到一個(gè)下標(biāo)i, 使得 str[0..i]是一個(gè)回文字符串
• 將str[0..i]記入臨時(shí)結(jié)果中
• 然后對(duì)于剩下的字符串str[i+1, end]遞歸調(diào)用前面的兩個(gè)步驟, 直到i+1 >= end結(jié)束
• 這時(shí)候, 我們找到了一組結(jié)果.
• 開(kāi)始回溯. 以回溯到最開(kāi)始的位置i為例. 從i開(kāi)始, 向右掃描, 找到第一個(gè)位置j, 滿足str[0..j]為一個(gè)回文字符串. 然后重復(fù)前面的四個(gè)步驟.

以字符串 "ababc" 為例.

• 首先找到 i = 0, "a"為回文字符串.
• 然后在子串"babc"中繼續(xù)查找, 找到下一個(gè) "b", 遞歸找到 "a", "b", "c". 至此我們找到了第一組結(jié)果. ["a", "b", "a", "b", "c"]
• 將c從結(jié)果中移除, 位置回溯到下標(biāo)為3的"b". 從"b"開(kāi)始向后是否存在str[3..x]為回文字符串, 發(fā)現(xiàn)并沒(méi)有.
• 回溯到下標(biāo)為2的"a", 查找是否存在str[2..x]為回文字符串, 發(fā)現(xiàn)也沒(méi)有.
• 繼續(xù)回溯到下標(biāo)為1的"b", 查找是否存在str[1..x]為回文字符串, 找到了"bab", 記入到結(jié)果中. 然后從下標(biāo)為4開(kāi)始繼續(xù)掃描. 找到了下一個(gè)回文字符串"c".
• 我們找到了下一組結(jié)果 ["a", "bab", "c"]
• 然后繼續(xù)回溯 + 遞歸.

實(shí)現(xiàn)

class Solution {
public:
    vector<vector<string>> partition(string s) {
        std::vector<std::vector<std::string> > results;
        std::vector<std::string> res;
        dfs(s, 0, res, results);
        return results;
    }
private:
    void dfs(std::string& s, int startIndex,
            std::vector<std::string> res,
            std::vector<std::vector<std::string> >& 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();
            }
        }
    }
};

Q2 回文字符串的最少分割數(shù)

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.

實(shí)現(xiàn)

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];
    }   
};