Part 6 – Dynamic Programming – Bottom Up solution using 1D array

Introduction

In earlier blogs about Dynamic Programming, brute force and Topdown approach have been utilized first to find solution, because they tend to be more intuitive.

• Part 1: introduces and differentiate between bottom up and top down solutions. Top down solution is often done by drawing a decision tree and using recursive calls to traverse the tree. Each node in the tree is a state, with one or more state variables. Bottom Up uses array to store and calculate value at each node, which is corresponding to the node in the decision tree.
• Part 2: introduces scenarios where each node in decision tree could have multiple variables.
• Part 3: introduces scenarios where each node in decision tree could have multiple variables.
• Part 4: introduces a common template, backtracking, that is usually used in top down solution.
• Part 5: explain some troubleshooting steps while solving top down solutions. It demonstrates that a decision tree is huge, and bad analysis of decision tree nodes, forward condition, backtracking condition could lead to error that happens very late while traversing the tree. Thus debugging the issue with a top down approach could be hard and time consuming.

This blog post introduces bottom up approach as the first approach. It still explains top down solution, but explains top down approach first to show that the solution could still be very straightforward and intuitive come up with.

Sample Problem: Word Break

Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Note that for example 3, although any word in wordDict could be made from input string s, the string s cannot be segmented to entirely. Segmentation here means that the string s is broken up, and the part that already matches a word in wordDict cannot be used to construct another matching word.

For example:

catsandog = "cats" + "and" + "og" . "og" is not in wordDict

catsandog = "cats" , but "sand" then cannot be part of the string segment.

Bottom up solution

First we should come up with an dynamic programming array dp[], where each element can indicate output of a state.

• the state: bool value indicating the substring from input s match a word in wordDict or not.
• state variable: index of the characters in the input string s.
  • d[i]= true if a substring matches the word in wordDict
• recurrence relation:
  • if a substring matches the word in wordDict, the substring should start from i - word.length()+1 and has the size of word.length(), where i is the index of the current character. (current state).
  • Condition 1: i == word.length() happens when the first segment match a word in wordDict
  • Condition 2: dp[i-word.length()]=true, the left word or previous segment on the left matchs a word in wordDict.

The following illustrate condition 1 and condition 2:

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp (s.length(), false);
        for (int i = 0; i < s.length(); i++ ){
            for (string word : wordDict){
                cout<<i;
                cout<<" "<<word<<endl;
                if (i >= word.length()-1){                  // check boundary condition

                    if (i == word.length()-1 ||             // Condition 1: possible fisrt match
                        dp[i-word.length()]                 // Condition 2: if the last string segment was found in wordDict
                       ){
                            string tmp = s.substr(i - word.length() + 1, word.length());
                            cout<<" substr: "<<tmp<<endl;
                            auto it = find(wordDict.begin(), wordDict.end(), tmp);
                            if  ( it != wordDict.end()){
                                dp[i] = true;
                                cout<<"match "<< tmp<<" at index "<<i<<endl;
                            }
                        }
                }
            }
        }
        return dp[s.length()-1];
    }
}; 

Top down solution:

Top down is done by drawing a decision tree, where each node is a state, and traversing the state is done by recursive function or by backtracking algorithm.

Intuitively, from the Bottom up solution, we have the idea that at each state, the input string is segmented to a left segment and a right segment.

If the left segment match a word in wordDict, at index i, then we look further on the right segment of the input string to find a match. When we look further, we actually traverse to the next node.

The following illustrates a string leet could be segmented into l and eet , le and et, lee nd t, leet and null and more. wb(eet) is the recursive call which indicates that eet could be further segmented in to e and et for example.

Suppose that the wordDict = {"l", "e", "ee", "le", "lee"}, we would have the following decision tree:

The decision tree shows that some branches are repeated, which could be cached.

We come up with the following dynamic programming values:

• state: indicates if the segments on the left and on the right could match a word in wordDict. Each state includes 2 condition:
  • Condition 1: true if segment on the left match a word in wordDict
  • Condition 2: true if segment on the right match a word or words in wordDict
• state variable are the substrings that are on the left or the right. We could get the substrings by the index of the middle character that divides the left and right segment. Thus we have only 1 state variable.

Code

#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std; 

// Memoization approach
class Solution {
public:
    map<string, int> cache;
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> word_set(wordDict.begin(), wordDict.end());
        // In the cache table, -1 stands for the state not yet reached,
        // 0 for false and 1 for true
        vector<int> cache(s.length(), -1);
        return wordBreakRecur(s, word_set, 0, cache);
    }

    bool wordBreakRecur(string& s, set<string>& word_set, int start, vector<int>&cache) {
        cout<<"---wordBreakRecur--- stringIndex: "<<start<<endl;
        if (start == s.length()) {
            return true;
        }
        
        // step 1: search cache for save value
        if (cache[start] != -1 ) {       // if a cache for a substring was saved, return its value
            cout<<"return cache"<<endl;
            return cache[start];        }; 
        int end;
        string substring;
        // step 2:  make recursive call, find result, save result to cache
        cout<<" --For loop Starts--"<<endl;
        for (end = start + 1; end <= s.length(); end++) {      // make recursive call, topdown
            substring = s.substr(start, end - start);
            if (word_set.find(substring) != word_set.end()) {           // Step2.1: Check first condition if left substring is found in wordDict
                if( wordBreakRecur(s, word_set, end, cache)) {            // Step2.2: Check second condition if right substring if found in wordDict       
                    cout<<"save cache "<<substring<<endl;
                    cache[start]=1;
                    return true;
                }      
            }   
        }
        {
            cout<<"save cache "<<substring<<" false"<<endl;
            return cache[start]=0;
        }
    }
};

int main(){
    vector<string> wordDict = {"hello", "world"};
    Solution sol;
    sol.wordBreak("hello", wordDict);
}