类似于subset
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> list;
if(s.empty()) return result;
dfs(0, result, list, s);
return result;
}
private:
void dfs(int pos, vector<vector<string>>& result, vector<string>& list, string s){
if(pos == s.size()){
result.push_back(list);
}
for(int i = pos; i < s.size(); i++){//
string substr = s.substr(pos, i + 1 - pos);
if(!isPalindrome(substr)) continue;
list.push_back(substr);
dfs(i+1, result, list, s);//因为这种类似于拼接的题目,subset之类的,取过的不能取, 只能往后取了,所以要是i+1
list.pop_back();
}
}
bool isPalindrome(string str){
if(str.empty()) return false;
int l = 0, r = str.size() - 1;
while(l <= r){
if(str[l] != str[r]){
return false;
}
l++;
r--;
}
return true;
}
};
网友评论