Find if a string is a concatenation of dictionary words

I had an interview recently with a well known auto-related company(that's all I'm gonna say !). I thought I would share the problem that I faced, how I solved it during the interview, and another simpler solution I found while up solving afterwards.

The Problem

Given a non-empty string s and a dictionary containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example:

Input: s = "DearReader", words = ["Dear", "Reader"].                                             Output: true                                                                                                       Explanation:  "DearReader" can be segmented as "Dear Reader", both parts are present in our dictionary.

The Solution I came up with,

Or the slow bulky and time consuming solution

When in doubt, go for recursion! And that's exactly what I did. After some iterations, I wrote a backtracking solution that looks like this:

class Solution {
public:
    bool backtrack(string s, set<string> st, int i) {
        if(i >= s.size())
            return true;
        
        for(int k = i+1; k <= s.size(); k++) {
            string ss = s.substr(i, k - i);
            if(st.count(ss) > 0 && backtrack(s, st, k)){
                return true;
            }
        }
        
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> st(wordDict.begin(), wordDict.end());
        return backtrack(s, st, 0);
    }
};

The gist of the solution above is if we go through the string and once we find a word, we call the function on the rest of the string.

This solution though, as many would conclude, is a very inefficient one. In fact, the overall time complexity amount to O(N^N). Since each time we have at most N choices for the indices and the overall depth of the recursive tree can be N.

The interviewer was kind enough to accept this solution. Though, for the sake of learning and upping my article word count game(haha!). We will look at two other solutions. The first builds on our backtracking one but uses memoization to make it more efficient. The second one is a dynamic programming, and surprisingly easy, solution.

Backtracking with Memoization

If we look at our previous solution, we might figure out that some cases are computed over and over. Memoization will enable us to skip these useless computations.

class Solution {
public:
    bool backtrack(string s, set<string> st, vector<int>& cache, int i) {
        if(i >= s.size())
            return true;
        
        if(cache[i] >= 0)
            return cache[i] == 1;
        
        for(int k = i+1; k <= s.size(); k++) {
            string ss = s.substr(i, k - i);
            if(st.count(ss) > 0 && backtrack(s, st, cache, k)){
                cache[i] = 1;
                return true;
            }
        }
        
        cache[i] = 0;
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> st(wordDict.begin(), wordDict.end());
        vector<int> cache(s.size(), -1);
        return backtrack(s, st, cache, 0);
    }
};

The memoization is simple. We keep an array of the size of the string and if the index we're at was previously computed, we return that value directly. However, the effect this has on the complexity is powerful. We end up with a time complexity of O(n^3). We go through the string once and for each index we go through all the following indices(N*(N+1)/2), plus we have one substring operation each time of complexity O(N).

Dynamic Programming

I didn't do a lot of dynamic programming problems, so it is not usually my go to method. But in this case, as we'll see, the solution is intuitive and easy to reason about.

Like the previous solution, we go through the string once till we find a word(or a previously marked breakable string. But this time we won't do a recursive call, and we would rather keep all our values in one array.

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> st(wordDict.begin(), wordDict.end());
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for(int i = 1; i <= s.size(); i++) {
            for(int j = 0; j < i; j++) {
                string sub = s.substr(j, i-j);
                if(dp[j] && st.count(sub) > 0) {
                    dp[i] = 1;
                    break;
                }
            }
        }
        
        return dp[s.size()] == 1;
    }
};