LeetCode OJ:Palindrome Partitioning
Palindrome Partitioning
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 =
アルゴリズム思想:深い暴力検索
ダイナミックプランニング
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"]
]
アルゴリズム思想:深い暴力検索
class Solution{
public:
int palindrome(string s,int l,int r){
while(r&&l<s.length()&&s[l]==s[r]){
l++;r--;
}
if(l<r)return 0;
return 1;
}
void dfs(string str,int k,vector<string> t,vector<vector<string>> &store){
if(k>str.length()-1){
store.push_back(t);
return;
}
for(int i=k;i<str.length();i++){
if(palindrome(str,k,i)){
t.push_back(str.substr(k,i-k+1));
dfs(str,i+1,t,store);
t.pop_back();
}
}
}
vector<vector<string>> partition(string s){
vector<vector<string>> store;
vector<string> t;
dfs(s,0,t,store);
return store;
}
};
ダイナミックプランニング
class Solution {
public:
vector<vector<string>> partition(string s) {
const int n=s.size();
bool p[n][n];
fill_n(&p[0][0],n*n,false);
for(int i=n-1;i>=0;--i)
for(int j=i;j<n;++j)
p[i][j]=s[i]==s[j]&&((j-i<2)||p[i+1][j-1]);
vector<vector<string>> result[n];
for(int i=n-1;i>=0;--i){
for(int j=i;j<n;++j){
if(p[i][j]){
const string palindrome=s.substr(i,j-i+1);
if(j+1<n){
for(auto v:result[j+1]){
v.insert(v.begin(),palindrome);
result[i].push_back(v);
}
}else{
result[i].push_back(vector<string>{palindrome});
}
}
}
}
return result[0];
}
};