Skip to content

Instantly share code, notes, and snippets.

@kishan-dhankecha
Created October 13, 2021 09:19
Show Gist options
  • Save kishan-dhankecha/5bff26e79b01c6437586fe65808df0f9 to your computer and use it in GitHub Desktop.
Save kishan-dhankecha/5bff26e79b01c6437586fe65808df0f9 to your computer and use it in GitHub Desktop.
Can construct function with memoization [JAVASCRIPT]
/// Write a function 'canConstruct(target, wordBank)' that accepts a
/// target string and an array of strings.
/// The function should return a boolean indicating whether or not the
/// 'target' can be constructed by concatenating elements of the
/// 'wordBank' array.
/// You may reuse elements of ‘wordBank' as many times as needed.
const canConstruct = (target, wordBank, memory = {}) => {
// Check in memory.
if (target in memory) return memory[target];
// Return obvious values to stop recursion.
if (target === '') return true;
// Iterate through wordBank array
for (let word of wordBank) {
if (target.indexOf(word) === 0) {
const suffix = target.slice(word.length);
if (canConstruct(suffix, wordBank, memory) === true) {
memory[target] = true;
return true;
};
}
}
memory[target] = false;
return false;
}
console.log(canConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'])); // true
console.log(canConstruct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar'])); // false
console.log(canConstruct('enterapotentpot', ['a', 'p`', 'ent`', 'enter`', 'ot`', 'o', 't'])); // false
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment