Can Construct with Tabulation

Updated: 01 February 2024

Problem

The same problem as the Can Construct Memoization Problem but implemented using the tabular style in the previous problems

In this case, we will store an index for each letter and the value of whether or not it is possible to start a substring from that position - if it is possible then we will go to the end of ths substring and mark that position as false

Tabulation Implementation

The implementation of this can be seen below:

1
export const canConstruct = (target: string, subs: string[]): boolean => {
2
  const table = new Array<boolean>(target.length + 1).fill(false);
3
  table[0] = true;
4

5
  for (let index = 0; index <= target.length; index++) {
6
    if (table[index]) {
7
      for (const sub of subs) {
8
        const fromIndex = target.slice(index);
9
        if (fromIndex.startsWith(sub)) {
10
          const nextIndex = index + sub.length;
11
          table[nextIndex] = true;
12
        }
13
      }
14
    }
15
  }
16

17
  return table[target.length];
18
};

In the above, the time complexity $O(m^2 *n)$ and space complexity $O(m^2)$

The reason we say $m^2$ and not $m$ in the time complexity is because of the array copy operation that we do to assign the latest value