lintcode136. 分割回文串

Jill ·

更新时间:2024-09-21

· 825 次阅读

给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.
返回所有可能的分割方案.

样例
样例 1:
输入: "a"
输出: [["a"]]
解释: 字符串里只有一个字符, 也就只有一种分割方式 (就是它本身)
样例 2:
输入: "aab"
输出: [["aa", "b"], ["a", "a", "b"]]
解释: 有两种分割的方式.
    1. 将 "aab" 分割成 "aa" 和 "b", 它们都是回文的.
    2. 将 "aab" 分割成 "a", "a" 和 "b", 它们全都是回文的.
注意事项
不同的方案之间的顺序可以是任意的.
一种分割方案中的每个子串都必须是 s 中连续的一段.

class Solution {
public:
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector> partition(string &s) {
        // write your code here
        if(s.size() <= 0) {
            return vector<vector >();
        }
        vector<vector > result;
        vector temp;
        search(s, 0, temp,result);
        return result;
    }
    void search(string &s,int cur,vector tmp,vector<vector> &res)
    {
        if(cur==s.size()) 
        {
            res.push_back(tmp);
            return;
        }
        else
        {
            for (int i = cur; i < s.size(); i++) {
                if(isPalindrome(s,cur,i))
                {
                    tmp.push_back(string(s,cur,i-cur+1));
                    search(s,i+1,tmp,res);
                    tmp.pop_back();
                }
            }
        }
    }
    bool isPalindrome(string s,int start,int end)
    {
        while(start<=end)
        {
            if(s[start]!=s[end]) return false;
            start++;
            end--;
        }
        return true;
    }
};

作者：Sinb妃

回文串

1024 个赞