首页 > 代码库 > LeetCode: Palindrome Partitioning [131]

LeetCode: Palindrome Partitioning [131]

2024-07-09 15:45:49   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"]
  ]

【题意】

    给定一个字符串s, 要求对s进行划分，划分后每个子串都是回文串。
    要求返回所有的划分情况


【思路】

    直观思路是使用逐层递归，先确定第一个点，然后确定第二个点，再确定第三个点，依次类推，这种方式的时间复杂度非常高。
    
    本题使用DP：先计算出任意两个位置i,j之间的子串是否是回文串，用IsPalindrome[i][j]表示。

    


【代码】

class Solution {
public:
    
    void getPartition(vector<vector<string> >&result, vector<string>&splits, int start, string&s, vector<vector<bool> >&isPal){
        //spits-已切分的结果，start-当前切分开始的位置
        if(start==s.length()){
            vector<string> newSplits = splits;
            result.push_back(newSplits);
            return;
        }
        
        for(int end=start; end<s.length(); end++){
            if(isPal[start][end]){
                splits.push_back(s.substr(start, end-start+1));
                getPartition(result, splits, end+1, s, isPal);
                splits.pop_back();
            }
        }
    }
    
    vector<vector<string>> partition(string s) {
        vector<vector<string> >result;
        int len=s.length();
        if(len==0)return result;
        
        vector<vector<bool> > isPal(len, vector<bool>(len, false));
        //初始化isPal[i][i]=true;
        for(int i=0; i<len; i++)
            isPal[i][i]=true;
        //初始化相邻两位字符构成的子串
        for(int i=0; i<len-1; i++)
            if(s[i]==s[i+1])isPal[i][i+1]=true;
        //判断其他i<j的位置
        for(int i=len-3; i>=0; i--)
            for(int j=i+2; j<len; j++)
                isPal[i][j]=(s[i]==s[j]) && isPal[i+1][j-1];
        
        //确定所有的组合
        vector<string> splits;
        getPartition(result, splits, 0, s, isPal);
        return result;
    }
};


联系
我们