All Construct

Updated: 01 February 2024

Problem

This problem is very similar to the previous question but now instead of counting the ways we can construct a string we want to return the the list of ways that the word can be constructed

Base Implementation

The implementation of this is pretty similar to the Count Construct problem but we return the list of combinations that make the input string

1
export const allConstruct = (target: string, parts: string[]): string[][] => {
2
  // for the base case there is one way to return the combination and that is the empty solution;
3
  if (target == "") return [[]];
4

5
  let permutations: string[][] = [];
6

7
  for (let part of parts) {
8
    if (target.startsWith(part)) {
9
      const restOfWord = target.slice(part.length);
10

11
      const current = allConstruct(restOfWord, parts);
12
      const joint = current.map((arr) => [part, ...arr]);
13
      permutations = [...permutations, ...joint];
14
    }
15
  }
16

17
  return permutations;
18
};

The complexity of this is the same as the Can Construct implementation with a time complexity $O(n^m)$ and space complexity of $O(n^m)$ since we always need to return a large list of subarrays of combinations

With memoization

We implement the memoization as in the previous examples

1
type Memo = Record<string, string[][]>;
2

3
export const allConstruct = (
4
  target: string,
5
  parts: string[],
6
  memo: Memo = {}
7
): string[][] => {
8
  if (target in memo) return memo[target];
9

10
  // for the base case there is one way to return the combination and that is the empty solution;
11
  if (target == "") return [[]];
12

13
  let permutations: string[][] = [];
14

15
  for (let part of parts) {
16
    if (target.startsWith(part)) {
17
      const restOfWord = target.slice(part.length);
18

19
      const current = allConstruct(restOfWord, parts, memo);
20
      const joint = current.map((arr) => [part, ...arr]);
21
      permutations = [...permutations, ...joint];
22
    }
23
  }
24

25
  memo[target] = permutations;
26
  return permutations;
27
};

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)$