Created
October 13, 2021 09:19
-
-
Save kishan-dhankecha/5bff26e79b01c6437586fe65808df0f9 to your computer and use it in GitHub Desktop.
Can construct function with memoization [JAVASCRIPT]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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