PINEAL.ME   Archives  About

Palindrome Partitioning

Questions

分隔回文串问题,共有两题,分别是搜索和动归的代表题型。刚碰到的时候理解比较难,单独拿出来看一看。

Palindrome Partitioning II

求最小的分割次数,一维的一个数组,满足动态规划的条件。

提示:动归字符串时基本上要把f[0]空出来,这样就需要n+1长度的一个数组来记录最优值。

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        if (len <= 1) return 0;

//用一个矩阵来记录子字符串s[i:j]是否为回文串

        vector<vector<bool> > mat = vector<vector<bool> >(len, vector<bool>(len, true));

        for (int i = len; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
//                if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j])
//                    isPal[i][j] = true;                
//很多答案给的是这样的判断方法,个人觉得没有下面的清楚,边界条件实际上就两种,要么i==j要么i和j靠在一起。其他就判断xSx是不是回文串(如果S是的话)              
                if (j == i) {
                    mat[i][j] = true;
                } else if (j == i + 1) {
                    mat[i][j] = (s[i] == s[j]);
                } else {
                    mat[i][j] = ((s[i] == s[j]) && mat[i + 1][j - 1]);
                }
            }
        }

        vector<int> cut(len + 1, INT_MAX);

// 真正的sequence DP: cut[i]表示到i的minCut
// 到位置i时候,就判断j+1到i是不是一个回文串(到角标就变成了和j , i-1)
// 就找所有比i小的j的位置上能切的minCut + 1(此时条件为上面那个矩阵)
//

        for (int i = 1; i < 1 + len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (mat[j][i - 1]) {
                    cut[i] = min(cut[i], 1 + cut[j]);
                }
            }
        }

        return cut[len];
    }
};

还有一个优化的解以后留着看。

Palindrome Partitioning

这题求的是具体的分隔方法,基本上就是DFS搜索加回溯的方法。

class Solution {
public:
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string s) {
        vector<vector<string> > result;
        if (s.empty()) return result;

        vector<string> palindromes;
        dfs(s, 0, palindromes, result);

        return result;
    }

private:
    void dfs(string s, int pos, vector<string> &palindromes,
             vector<vector<string> > &ret) {

        if (pos == s.size()) {
            ret.push_back(palindromes);
            return;
        }

        for (int i = pos + 1; i <= s.size(); ++i) {
            string substr = s.substr(pos, i - pos);
            if (!isPalindrome(substr)) {
                continue;
            }

            palindromes.push_back(substr);
            dfs(s, i, palindromes, ret);
            palindromes.pop_back();
        }
    }

    bool isPalindrome(string s) {
        if (s.empty()) return false;

        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] != s[n - i - 1]) return false;
        }

        return true;
    }
};

当状态可以用index 从 0 到 i 可以表示,一维DP往往是足够的。 当过去的状态不能从i 开始, 那么i-j开始,需要用二维DP。

Search   DFS   Backtracking   Dynamic Programming