Count Construct
Updated: 01 February 2024
Problem
Given a target string and a list of strings return the number of ways that the items in the string list can be combined to build the string in the target
An example of what we want to do is:
1canConstruct(abcdef, [ab, cd, ef]) = 12canConstruct(abcdef, [ab, cd]) = 03canConstruct(abcdef, [ab, cd, cdef, ef]) = 2
In general it will probably be easier to create a shorter string than a longer one
We can consider a base case where:
1canConstruct('', [a,b,c]) = true
Base Implementation
The implementation of this is pretty similar to the Can Construct problem
1export const countConstruct = (target: string, parts: string[]): number => {2 if (target == "") return 1;3
4 let permutationCount = 0;5
6 for (let part of parts) {7 if (target.startsWith(part)) {8 const restOfWord = target.slice(part.length);9
10 const currentCount = countConstruct(restOfWord, parts);11 permutationCount += currentCount;12 }13 }14
15 return permutationCount;16};
The complexity of this is the same as the Can Construct implementation with a time complexity and space complexity of
With memoization
We implement the memoization as in the previous examples
1type Memo = Record<string, number>;2
3export const countConstruct = (4 target: string,5 parts: string[],6 memo: Memo = {}7): number => {8 if (target in memo) return memo[target];9 if (target == "") return 1;10
11 let permutationCount = 0;12
13 for (let part of parts) {14 if (target.startsWith(part)) {15 const restOfWord = target.slice(part.length);16
17 const currentCount = countConstruct(restOfWord, parts, memo);18 permutationCount += currentCount;19 }20 }21
22 memo[target] = permutationCount;23 return permutationCount;24};
The complexity of this is the same as the Can Construct memoized implementation with a time complexity and space complexity of