Published on

[Dynamic Programming] Can Construct

Problem

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.

Brute Force

const canConstruct = (target, wordBank) => {
	// base case
	if(target === '') return true;

	for(let word of wordBank) {
		// if target starts with word, try the remaining
		if(target.startsWith(word)) {
			if(canConstruct(target.slice(word.length), wordBank)) {
				return true
			}
		}
	}

	return false;
}

Memoization

const canConstructMemo = (target, wordBank, memo = {}) => {
	if(target in memo) return memo[target]

	// base case
	if(target === '') return true;

	for(let word of wordBank) {
		if(target.startsWith(word)) {
			if(canConstructMemo(target.slice(word.length), wordBank, memo)) {
				memo[target] = true
				return true
			}
		}
	}

	memo[target] = false
	return false;
}

Tabulation

const canConstructTab = (target, wordBank) => {
	// table stores if it is possible to construct the target up to index
	let table = Array(target.length + 1).fill(false)
	// empty string is true, and this is our base case.
	table[0] = true;

	for(let i = 0; i <= target.length; i++) {
		// table at i is true, then word.length later is also true
		if(table[i] === true) {
			for(let word of wordBank) {
				if(target.slice(i, i + word.length) === word) {
					table[i + word.length] = true
				}
			}
		}
	}

	return table[target.length]
}

Reference