Backtracking and Memoization

Backtracking is a technique that we talked about when solving permutations. Let’s look at another problem where backtracking is the key to solving it.

Problem: Given a non-empty string `s` and a dictionary, `dict` determine if `s` can be segmented into a sequence of one or more dictionary words.

Algorithm 1:

Using a backtracking approach find the first substring that is a valid dictionary word and then recurse on the remaining string to see if it can be further split.

splitWord(s[0..n]) = s[0..i] + splitWord(s[i+1..n]) where s[0..i] is a dictionary word.

If splitWord(s[i+1..n]) fails, then we backtrack to index i where the last match was found and scan for the next valid dictionary word.

splitWord(s[0..n]) = s[0..j] + splitWord([j..n]) where j > i and s[0..j] is a dictionary word

bool splitWord(string s, set<int> dict)
{
   if(s.length() == 0)
     return true;
 
   for(int i=1;i<=s.length();i++) {     
      string temp = s.substr(0,i);     

      if((dict.count(temp)!=0) && 
         splitWord(s.substr(i))) {
         return true;
     }
   }
   return false;
}

Example
s: catsanddogs
dict: {cat, cats, and, dogs}
1. {cat, sanddogs} //cat is a match
2. {sanddogs} — no match
   1. return to step 1 and extend from the last match
4. {cats, anddogs} //cats is a match
5. {anddogs}
6. {and, dogs} //and is a match
7. {dogs} — matched.
Answer: True -> {cats, and, dogs}
Step 2 is where we backtracked to last match and extended the string to find next possible match.

Run time for this solution is O(2^n) because in the worst case each character of the string might be present in the dictionary.

Example: 
s: aaab
dict: {a, aa, aaa}
In the above case each letter is a valid dictionary word. So, we have to do recursive call on every possible prefix.
1. {aaab} -> {a, aab} 
2. {aab} -> {a, ab} 
3. {ab} -> {a, b} 
4. {b} //no match, 
    2. {aab} -> {aa, b} //return to step 2
5. {b} //no match 
    1. {aaab} -> {aa, ab} 
6. {ab} -> {a, b} 
7. {b} //no match 
    1. {aaab} -> {aaa, b} 
8. {b} //no match 

// 2^n-1 calls. Also, in each call we have to iterate through the length of the string O(n).
T(n) = n + T(n-1) + T(n-2) + .. T(1)
T(n) = n + n-1 + 2*T(n-2) + 2*T(n-3) + .. T(1)
T(n) = 2n — 1 + 2*T(n-2) + 2*T(n-3)+2*T(n-4)
T(n) = 4n — 5 + 4*T(n-3) + 4*T(n-4)
T(n) = 8n — 17 + 8*T(n-4)
T(n) = (n*2^n-1) = O(2^n)

The run time can be reduced if we memorize the solution. E.g., As part of T(n-2) we solve T(n-3) and remember the solution for T(n-3). When we start to solve T(n-1) we can reuse the solution of T(n-3) without going into further recursive calls.

bool splitWord(string s, set<string> &visited, set<string> dict)
{
   if(s.length() == 0)
   return true;
 
   for(int i=1;i<=s.length();i++) {
   string temp = s.substr(0,i);
   if(dict.count(temp)!=0 && 
      visited.count(s)==0)
   {
     if(splitWord(s.substr(i), visited, dict)) {
        return true;
      } 
      visited.insert(s.substr(i));
     }
   }
   return false;
 }

Example: 
s: aaab
dict: {a, aa, aaa}
1. {aaab} -> {a, aab} 
2. {aab} -> {a, ab} 
3. {ab} -> {a, b} 
4. {b} //no match
   3. insert b in visited
   2. insert ab in visited
   2. {aab} -> {aa, b} //skip as b is visited
   1. insert aab in visited
   1. {aaab} -> {aa, ab} //skip as ab is visited
   1. {aaab} -> {aaa, b} // skip as b is visted. 
In total we have made only n-1 recursive calls for a string of length n. However, we travese a string of length n in each recursive call.
T(n) = n+T(n-1) = 2n + T(n-2) = 3n + T(n-3) = n²