Count Construct with Tabulation

Updated: 01 February 2024

Problem

The same problem as the Count 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 how many substrings can start 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:

dynamic-programming/tabulation/count-construct.ts
1
export const countConstruct = (target: string, subs: string[]): number => {
2
  const table = new Array<number>(target.length + 1).fill(0);
3
  table[0] = 1;
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] += table[index];
12
        }
13
      }
14
    }
15
  }
16


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

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

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