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;
};
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?
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....