LC: Concatenated Words

Viewed 37

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

var findAllConcatenatedWordsInADict = function(words) {
    let m = new Map(), memo = new Map();
    let res = [];
    for (let i = 0; i < words.length; i++) {
        m.set(words[i], 1);
    }
    for (let i = 0; i < words.length; i++) {
        if (isConcat(words[i], m, memo)) res.push(words[i]);
    }
    return res;
};

function isConcat(word, m, memo) {
    if (memo.has(word)) return memo.get(word);
    for (let i = 1; i < word.length; i++) {
        let prefix = word.slice(0, i);
        let suffix = word.slice(i);
        if (m.has(prefix) && (m.has(suffix) || isConcat(suffix, m, memo))) {
            memo.set(word, true);
            return true;
        }
    }
    
    memo.set(word, false);
    return false;
};

  1. Still trying to wrap my head around the solution why do we call the isConcat function ONLY on the suffix that we generate from words[i] and not prefix?

  2. Further, I have tried running various test cases ["cat","cats","dog","dogcatsdog","rat","ratcatdogcat"].

It seems like we do not call the isConcat function on the first suffix that is generated from word[0] ('at'). However, we do seem to call it on 'catsdog' as part of the "dogcatsdog" word so I'm not sure how the logic works as to how it chooses which suffixes to call on....

1 Answers

My mistake was misreading the code and assuming that the following conditions had to return true for a valid concatenated word:

Map has both prefix and suffix; OR

isConcat(suffix) returns true

In fact, prefix is already known to be in map (since map.has(prefix) must be true in order to reach the recursive call in the first place!). Thus, a concatenated word is only valid if the suffix is also an element of map or it's another concatenated word. map.has(suffix) tests if the suffix is in map, while isConcat(suffix, map, memo) tests whether the suffix is also a concatenated word.

Related