traversing string ,and split it one char by next, if find the splited left word in dict, recursiving the remaining right substring. in this way, it will make sure find a solution, but also traversing all unnecessary possibilites. and need design a class variable to stop the dfs()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool found = false;
bool(string s, unordered_set<string>& dict){
string left, right ;
if(s.size() == 0 || s.empty())
{
found = true;
return found;
}
for(int i=0; i<=s.size(); i++)
{
left = s.substr(0, i);
right = s.substr(i, s.size()-i);
if(dict.find(left) != dict.end())
{
dfs(right, dict);
}
}
return found;
};
bfs
as mentioned above, dfs goes to all possibile branches, which is not required. bfs is like a greedy way, to find out one working solution and done.
also need keep track of searched left sub-strings, since the remaining right sub-strings may can not find a matched from dict, then the left sub-string is not acceptable, so the left sub-string need move one char further.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
boolbfs(string s, unordered_set<string>& dict)
{
int len = s.size();
string s1, q, left, right;
queue<string> sq;
sq.push(s);
string tmp ;
while(!sq.empty()){
tmp = sq.front(); sq.pop();
int i=0;
s1 = s ;
while(!s1.empty() && i <= s1.size())
{
if(tmp == s){
left = s1.substr(0, i);
right = s1.substr(i, s1.size()-i);
}else
{
left = s1.substr(0, i+tmp.size());
right = s1.substr(i+tmp.size(), s1.size()-i-tmp.size());
}
i++;
if(dict.find(left) != dict.end())
{
q += left ;
sq.push(left);
s1 = right;
i = 0;
}
}
}
this bfs is not good design. a pretty simple sample code
近期评论