word break with dfs & bfs

Posted on |

leetcode 139

dfs

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 dfs(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
  bool bfs(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()); ///will dead-cycle 
        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