首页 > 代码库 > Palindrome Partitioning

Palindrome Partitioning

2024-07-02 03:16:10   222人阅读

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

思路：这道题是说对一个字符串做处理，找出这个字符串包含的所有回文序列。典型的递归回溯方法。首先定义一个判断字符串是否回文字符串，然后用深度搜索遍历方法，查找目标字符串序列。满足条件则先push到path中，不符合则pop。等index==s.size()是将path push到result。在进行深度搜索。
class Solution {
public:
    bool IsPalindrome(string s,int start,int end)
    {
        while(start<end)
        {
            if(s[start]!=s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
    void DFS(vector<vector<string> > &result,vector<string> &path,string &s,int index)
    {
        if(index==s.size())
        {
            result.push_back(path);
            return;
        }
        for(int i=index;i<s.size();i++)
        {
            if(IsPalindrome(s,index,i))
            {
                path.push_back(s.substr(index,i-index+1));
                DFS(result,path,s,i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string> > result;
        vector<string> path;
        result.clear();
        path.clear();
        if(s=="")
            return result;
        DFS(result,path,s,0);
        return result;
    }
};

 

 


联系
我们