Can Construct

Updated: 01 February 2024

Problem

Given a target string and a list of strings return a boolean that indicates if 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]) = true
2
canConstruct(abcdef, [ab, cd]) = false

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

We can work on shrinking the string by stepping and splitting off subscrings in our input data ensuring that we do not break the sequencing of the initial string, so we do not remove any segments from the middle of the string

We will split off substrings if they are within the start of our initial string

1
export const canConstruct = (target: string, parts: string[]): boolean => {
2
  if (target == "") return true;
3

4
  for (let part of parts) {
5
    if (target.startsWith(part)) {
6
      const restOfWord = target.slice(part.length);
7

8
      const result = canConstruct(restOfWord, parts);
9

10
      if (result) return true;
11
    }
12
  }
13

14
  return false;
15
};

In this implementation the height of this tree can be the length of the target word $m$, for every element we would do a check which is $n$, in this case the time complexity is $O(n^m * m)$ (the last $m$ because we’re slicing the string on each iteration). The space complexity is the at most the length of our string of $m$ and the new string we have that is maybe also of length $m$, the space complexity is the $O(m^2)$

With memoization

We implement the memoization as in the previous examples

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

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

11
  for (let part of parts) {
12
    if (target.startsWith(part)) {
13
      const restOfWord = target.slice(part.length);
14

15
      const result = canConstruct(restOfWord, parts, memo);
16

17
      if (result) {
18
        memo[target] = result;
19
        return true;
20
      }
21
    }
22
  }
23

24
  memo[target] = false;
25
  return false;
26
};

When we memoize this we are removing subtrees, this way we cut down the width of our tree. In the act of memoizing we define a map that stores the result of each substring which is of size $m$, the overall time complexity is the $O(n * m^2)$ and a space complexity of $O(m^2)$