In my last post I attempted this problem, but got the requirements flipped.

The problem

So in this problem, I need to see if I can complete a given string using words from a "dictionary". I can use words multiple times.

I watched the Neetcode video on how to solve this, but will try to solve this from memory. This is a dynamic programming problem, wherein I can perform computations and cache them for future use.

The way to solve this is to start from the back and move progressively toward the front. Let's say I have the string newyorkknickshavecoolkicks and I have the dictionary [icks, kicks, cool, have, nick, knicks, york, new]. I'd start by comparing the final l characters against each of the words in the dictionary, with l representing the length of each dictionary word. So in this case, both the words kicks and icks would pass here. From there I'd move my endpoint back to the char previous to the found word and perform the same operation.

So we'd have index inputString.length - foundDictionaryWord.length - 1, as found indices. We're basically building a node structure of found indices and word lengths until we get to the front of the word - if we even make it that far. If the first char in the word is a found node, we then work back through the nodes by found word length, and if we make it to the end, our result is True. I realize I get to choose breadth first or depth first search, as I can start with the first found word and continue from there, or I can search every word at ever level and then continue with the found words. I'll follow up on that to see if it matters.

The metaphor I like to describe this problem is I need to find a safe path to walk from beginning to end. I start at the end and work backwards. If a word in my dictionary matches the substring of current index to the end of the word length, and the next index after that substring is marked as a "safe" index (that index === true), then the current index is also safe. We work all the way back to the first index. The value of the first index, true or false, is the answer.

Okay - time to code.

Coding the solution -

function wordBreak(s: string, wordDict: string[]): boolean {
    const foundMap = Array.from({ length: s.length }).map(val => false);
    foundMap[s.length] = true;
    for (let i = s.length - 1; i >= 0; i--) {
        wordDict.forEach(word => {
            const wordLength = word.length;
            if (wordLength + i - 1 < s.length) {
                const wordCandidate = s.slice(i, wordLength + i);
                const anchorValue = foundMap[wordLength + i];
                if (anchorValue && word == wordCandidate) {
                    foundMap[i] = true
                }
            }
        })
    }
    return foundMap[0]
};

Parting thoughts

This project wrecked me for a bit. This is the first Dynamic Programming problem I've tackled. I've looked into it a bit more, and it qualifies as dynamic programming, as I'm performing the same "subproblem" on repeat and caching the result.

Very ready for the next problem.