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:

1
canConstruct(abcdef, [ab, cd, ef]) = 1
2
canConstruct(abcdef, [ab, cd]) = 0
3
canConstruct(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:

1
canConstruct('', [a,b,c]) = true

Base Implementation

The implementation of this is pretty similar to the Can Construct problem

1
export 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 $O(n^m * m)$ and space complexity of $O(m^2)$

With memoization

We implement the memoization as in the previous examples

1
type Memo = Record<string, number>;
2

3
export 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 $O(n * m^2)$ and space complexity of $O(m^2)$