palinedrome partition with dfs & bfs

Posted on |

parlindrome partition

leetCode 131 a sample code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int depth, string s){
  if(depth == s.size()){
    v.push_back(v1);
  }
  if(depth<s.size()){
    for(int i=depth; i<s.size(); i++){
      //left substring 
      if(palindrome(s.substr(depth, i-depth+1))){
        v1.push_back(s.substr(depth, i-depth+1));
        dfs(i+1, s);
        v1.pop_back();  
      }
    }
  }  
}

1) each col in the table is one way to partition the string.e.g. aab. col_1 , left string a is palindrome, v1=[a]; feed right string ab to dfs(i+1, s)(depth=0, i=depth)

1 2 3
a a a
a a
a b
b b

1.1) col1_1, left string a is palindrome, v1=[a, a];
feed right string b into dfs(i+1, s) (depth=1, i=depth)

1 2
a a
b
b

1.1.1) b will push into v1, make v1=[a, a, b], feed into dfs(i+1, s) (depth=2, i=depth), which will return since depth==s.size().

the above dfs()(depth=2, i=depth) returned, the immediate next step is b pop out from v1; also now is the finished of dfs()(depth=1, i=depth), so the immediate next step is the second a pop out.

1.1.2) so now go to (depth=1, i=depth+1), push ab into v1, making v1=[a, ab] . but ab is not palindrome, return immediately, then pop out ab.

1.2) at this time, the very outside dfs()(depth=0, i=depth) is all done, so pop the first a in v1; and go to (depth=0, i=depth+1); then (depth=0, i=depth+2)…

recursive of DFS

another example of recursive dfs. leetcode 129 sum root of leaf numbers

dfs is used to find all the solutions, in a way to go through each branch in the same level first, then go into the next level.

to traverse all solutions(branches), also need to mark traversing/traversed branches. so usually need:

to push ->  current traversing element
to pop -> traversed element

and a container to hold all solutions.

if design recursive with returned value, consider the critical condition. e.g. what suppose to return when the last element, and usually design the returned value as local variable in each recursive function, rather than a global variable.

one more thing is about the traversing direction, from left to right end, then when coding make sure the direction is consistent at all times.

BFS to find mini cuts

DFS is used to solve the kind of problem: traversal all possible solutions; leetcode 132 askes for the mini cuts, once find out the mini-cuts solution, done, no traverse all possibilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// define done, cut as class member variable 
void bfs(string s, bool& done){
  int len = s.length();
  string left, right;
  int i =0;
  while(!done && i<len){
    left = s.substr(0, len-i); //starting from the longest left string
    right = s.substr(len-i, i);
    if(palindrome(left)){
        cut++;
        if(palindrome(right))
        {
          done = true ;
        }else {
            bfs(right, done);
        }
    }
    i++;
  }
}