Word Break Problem

Given a string s and an array of words we have to check if that string can be formed by using those words in any order possible.

This problem is known as word break problem.

Example

Input:
s = "applepenapple";
words = ["apple", "pen"];

s = "catsandog";
words = ["cats", "dog", "sand", "and", "cat"]

Output:
true
false

Note: you can repeat the words any number of time you want like you have see in the first example.

Naive solution for word break problem

The most approach is to use brute force approach to check if the string can be formed or not.

Conceptually this is how it works

• Use a set to store only the unique words from dictionary of words given.
• Then use a function and check if there is a substring in the string which is also present in the word set or not.
• If it is present then call the same function recursively and check if there a substring after the current one and keep on doing this till there is sub-string available.
• If exists then return true else return false.

const wordBreak = (s, wordDict) => {
    // Initiate the start index to run the loop
    let start = 0;

    //Recursive functions
    return wordBreakRecursive(s, wordDict, start);
};

const wordBreakRecursive = (s, wordDict, start) =>{

    // Create a wordDic Set * not necessary we can use array itself
    let wordSet = new Set(wordDict);

    // Check for the start and s.length
    if(start == s.length) {
        return true
    }

    // run the loop from start + 1 because last index of previous recursive plus + 1 to move forward
    // ex - apple which ends at index 4 so to run the loop which should start at code which is index 5
    for(let end = start + 1; end <= s.length; end++) {

        // Check for substring exist in word Dic and also check for recursive return true where we pass end index which is start of recursive function
        if(wordSet.has(s.substring(start, end)) && wordBreakRecursive(s, wordDict, end)) {
            return true;
        }
    }

    // Return false if we did not find any match and recursive function return false
    return false;

}

Input
console.log(wordBreak("applepenapple",["apple", "pen"]);

Output:
true

Time complexity: O(n ^ 3).
Space complexity: O(n).

---

Using dynamic programming to solve the word break problem.

Dynamic programming follows a principle of storing the already solved sub-solution and reusing it to get the final solution. Thus we use extra memory to solve the problem faster.

The above naive approach can be optimized by using memoization.

const wordBreak = (s, wordDict) => {
    // Initiate the start index to run the loop
    let start = 0;

    // Create a memo array
    const memo = new Array(s.length);

    //Recursive functions
    return wordBreakRecursive(s, wordDict, start, memo);
};

const wordBreakRecursive = (s, wordDict, start, memo) => {

    // Create a wordDic Set * not necessary we can use array itself
    let wordSet = new Set(wordDict);

    // Check for memo value
    // If memo value exist than we can directly keep the recursive and return the value so that we don't need to repeat the recursive path where we already pass
    if(memo[start] !== undefined) {
        return memo[start];
    }

    // Check for the start and s.length
    if(start == s.length) {
        return true
    }

    // run the loop from start + 1 because last index of previous recursive plus + 1 to move forward
    // ex - apple which ends at index 4 so to run the loop which should start at code which is index 5 
    for(let end = start + 1; end <= s.length; end++) {

        // Check for substring exist in word Dic and also check for recursive return true where we pass end index which is start of recursive function
        if(wordSet.has(s.substring(start, end)) && wordBreakRecursive(s, wordDict, end, memo)) {
            return memo[start] = true;
        }
    }
	// Return the memo for start index if did not match
    return memo[start] = false;

}

Time complexity: O(n ^ 2).
Space complexity: O(n).