LeetCodeのDFS深さ優先ループ
1. Palindrome Partioning II
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 =
2. Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s =
A solution is
Analysis:
For the "Return all"problems, usually DFS or BFS will work well.
In this problem, a DFS with a simple cutting edge condition will pass all the test cases.
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"]
]
は、DFSを使用している可能性のあるすべての結果を出力します.bool isPalindrome(string &s, int start, int end){
while(start < end){
if(s[start] != s[end])
return false;
start++, end--;
}
return true;
}
void DFSPalin(vector<vector<string>> &result,
vector<string> solu,
string &s,
int start){
if(start == s.size()){
result.push_back(solu);
return;
}
for(int i= start; i<s.size();i++){
if(isPalindrome(s,start,i)){
solu.push_back(s.substr(start,i-start+1));
DFSPalin(result,solu,s,i+1);
solu.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> solution;
DFSPalin(result,solution,s,0);
return result;
}
2. Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s =
"catsanddog"
, dict = ["cat", "cats", "and", "sand", "dog"]
. A solution is
["cats and dog", "cat sand dog"]
. Analysis:
For the "Return all"problems, usually DFS or BFS will work well.
In this problem, a DFS with a simple cutting edge condition will pass all the test cases.
void dfsWordBreak(string &s,
int st,
vector<int>&sp,
unordered_set<string> &dict,
vector<string> &result,
vector<vector<bool>> &mp){
if(st>=s.size()){
string str = s;
for(int i=0;i<sp.size()-1;i++){
str.insert(sp[i]+i," ");
}
result.push_back(str);
}else{
for(int j=0;j<mp[st].size();j++){
if(mp[st][j]==true){
sp.push_back(j+1);
dfsWordBreak(s,j+1,sp,dict,result,mp);
sp.pop_back();
}
}
}
}
vector<string> wordBreak2(string s, unordered_set<string> &dict) {
vector<string> result;
vector<vector<bool>> mp(s.size(),vector<bool>(s.size(),false));
for(int i=0;i<s.size();i++){
for(int j=i;j<s.size();j++){
if(dict.find(s.substr(i,j-i+1))!=dict.end())
mp[i][j] = true;
}
}
bool flag = false;
for(int i=0;i<s.size();i++){
if(mp[i][s.size()-1])
{flag = true;
break;}
}
if(!flag) return result;
vector<int>sp;
dfsWordBreak(s,0,sp,dict,result,mp);
return result;
}