Word break problem

139. Word Break

https://leetcode.com/problems/word-break/description/

1. We have given dictionary words let’s say wordDict = [“leet”,”code”]
2. Given a string s = “leetcode” , return true if s can be segmented into a sequence of one or more dictionary words.

Approach#1 Dynamic Programming

1. f(i) returns true if i...n of string s can be segmented into sequences using dictionary words.
2. At level i , we have choices to break it into all possible substring i to j, where j tarting from i to n .
3. But not every choices are valid. Only substring which exist in dictionary is a valid choices.
4. It means we can try our recursion to all these valid choices only.
5. If any of child recursion return true then we can claim that f(i) is valid otherwise false .

Since f(i) repeat itself therefore we can apply memoization. Time complexity of code would reduced to O(n*n).

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    const set = new Set(wordDict);
    const n = s.length;
    // dp(i) represent if i...n is valid word break
    const dp = new Array(n).fill(null);
    const recursion = i => {
        // empty string can be build without using any words from dictionary
        if (i === n) {
            dp[i] = true;
            return true;
        }
        if(dp[i] !== null) {
            return dp[i]
        }
        // Try all next substring
        for (let j = i; j < n; j++) {
            const word = s.substring(i, j + 1);
            if (set.has(word)) {
                // This is a valid choice
                if(recursion(j + 1)) {
                    dp[i] = true;
                    return dp[i];
                }
            }
        }
        dp[i] = false;
        return dp[i];
    }
    return recursion(0);
};

Approach#2: Use Trie with DP

Approach#3: Using BFS

472. Concatenated Words

https://leetcode.com/problems/concatenated-words/

1. We have given an array of words words = [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”] .
2. Return all the concatenated words in the given list of words.
3. A concatenated word is a string comprised entirely of at least two shorter words (not necessarily distinct) in the given array.

Approach: based on word break problem

1. For each word, we can call wordBreak(s) method we have solved in the above problem.
2. A slight modification in wordBreak(s) is required to avoid using the same word in the dictionary.
3. Time complexity would be O(n^3)

Following is the code to implement this algorithm.

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function (words) {
    const set = new Set(words);
    // A modified wordBreak to ignore same word from dictionary
    const wordBreak = s => {
        const n = s.length;
        // dp(i) represent if i...n is valid word break
        const dp = new Array(n).fill(null);
        const recursion = i => {
            // empty string can be build without using any words from dictionary
            if (i === n) {
                dp[i] = true;
                return true;
            }
            if (dp[i] !== null) {
                return dp[i]
            }
            // Try all next substring
            for (let j = i; j < n; j++) {
                const word = s.substring(i, j + 1);
                // Slight modification to avoid same word
                if (s!== word && set.has(word)) {
                    // This is a valid choice
                    if (recursion(j + 1)) {
                        dp[i] = true;
                        return dp[i];
                    }
                }
            }
            dp[i] = false;
            return dp[i];
        }
        return recursion(0);
    }
    // Try wordbreak problem for all the string by ignoring self
    const ans = [];
    for (const s of words) {
        if (wordBreak(s)) {
            ans.push(s);
        }
    }
    return ans;
};

140. Word Break II

https://leetcode.com/problems/word-break-ii/description/

1. Given a string s = catsanddog
2. And dictionary wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
3. Add spaces in s to construct a sentence where each word is a valid dictionary word.
4. Return all such possible sentences in any order.
5. In the above example, the answer would be [“cats and dog”,”cat sand dog”]

Approach

This is the same problem as word break, the only difference is, that now we need to construct all the possible answers. We can do it in two passes.

1. In pass 1, simply run the wordBreak to build the dp.
2. In pass 2, construct an answer based on dp.

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function (s, wordDict) {
    const set = new Set(wordDict);
    const n = s.length;
    // dp(i) represent if i...n is valid word break
    const dp = new Array(n).fill(null);
    // Pass1: Build dp
    const recursion = i => {
        // empty string can be build without using any words from dictionary
        if (i === n) {
            dp[i] = true;
            return true;
        }
        if (dp[i] !== null) {
            return dp[i]
        }
        // Try all next substring
        let ans = false;
        for (let j = i; j < n; j++) {
            const word = s.substring(i, j + 1);
            if (set.has(word)) {
                // This is a valid choice
                if (recursion(j + 1)) {
                    ans = true;
                }
            }
        }
        dp[i] = ans;
        return ans;
    }
    recursion(0);
   // Pass 2: construct ans
    const output = [];
    const constructAns = (i, result) => {
        // Base case: Empty string return
        if (i === n) {
            output.push(result.join(' '));
            return;
        }

        // Try all possible substring
        for (let j = i; j < n; j++) {
            const word = s.substring(i, j + 1);
            if (set.has(word) && dp[j + 1]) {
                result.push(word);
                constructAns(j + 1, result);
                result.pop();
            }
        }
    }
    constructAns(0, []);
    return output;
};

691. Stickers to Spell Word

https://leetcode.com/problems/stickers-to-spell-word/description

We are given n different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

Example 1:

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation:
We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Approach #1: Brute force

We can use recursion approach to solve this problem.

1. Will scan every characters in the target. This will act as a level i.e. f(i) which represent target in the range of 0....i
2. All the stickers are available options to choose for the target[i] char.
3. But not all stickers are valid options, only stickers with the target[i] char are the valid option.
4. Mark the char used in that sticker if decided to choose.

Above code will run (m^n) time complexity which will not work.

Approach #2: Use subsequence approach

1. We don’t need to match all the chars in the target in sequence with the sticker.
2. When we pick a sticker, then will try to match all the chars in sticker in the target until exhausted.
3. Use remaining target to run the recursion again.
4. Use memoization to run it in O(2^n)

Following is code for reference.

/**
 * @param {string[]} stickers
 * @param {string} target
 * @return {number}
 */
var minStickers = function (stickers, target) {
    const m = stickers.length;
    const n = target.length;
    // Build char freq for each strickers
    const stickersFreq = [];
    for (const sticker of stickers) {
        const map = new Map();
        for (const chr of sticker) {
            map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
        }
        stickersFreq.push(map);
    }
    // dp(subsequence, min_stickers)
    const dp = new Map();
    const recursion = (word, stickerFreq) => {
        if (dp.has(word)) {
            return dp.get(word);
        }
        // if not sticker is selected then initialize count with 1
        let count = stickerFreq.size === 0 ? 0 : 1;
        const remainingTarget = [];
        // Check each char
        for (const chr of word) {
            if (stickerFreq.has(chr) && stickerFreq.get(chr) > 0) {
                stickerFreq.set(chr, stickerFreq.get(chr) - 1);
            } else {
                remainingTarget.push(chr);
            }
        }

        if (remainingTarget.length > 0) {
            const remaining = remainingTarget.join('');
            let used = Number.MAX_SAFE_INTEGER;
            // Try all possible stickers
            for (stickerFreq of stickersFreq) {
                // skip sticker if first char of remaining target doesn't exist
                if (!stickerFreq.has(remaining[0])) {
                    continue;
                }
                used = Math.min(
                    used,
                    recursion(remaining, new Map(stickerFreq))
                )
            }
            dp.set(remaining, used);
            count += used;
        }
        return count;

    }
    const result = recursion(target, new Map());
    if (result === Number.MAX_SAFE_INTEGER) {
        return -1;
    }
    return result;
};

Happy coding :-)