LeetCode: Stamping The Sequence Solution

1/**
2 * getAllStampPatterns('abc')
3 * => a**, ab*, abc, *b*, *bc, **c
4 */
5const getAllStampPatterns = stamp => {
6  const stampPatterns = new Set() // for O(1) lookup
7  const stampN = stamp.length
8  for (let i = 0; i < stampN; i++) {
9    for (let j = i; j < stampN; j++) {
10      stampPatterns.add(
11        "?".repeat(i - 0) +
12          stamp.substring(i, j + 1) +
13          "?".repeat(stampN - 1 - j)
14      )
15    }
16  }
17  return stampPatterns
18}
19
20/**
21 * @param {string} stamp
22 * @param {string} target
23 * @return {number[]}
24 */
25var movesToStamp = function (stamp, target) {
26  const targetN = target.length
27  const stampN = stamp.length
28  const beginningSequence = "?".repeat(targetN)
29  const stampPatterns = getAllStampPatterns(stamp)
30  const res = []
31
32  checkIfAllStamped: while (target !== beginningSequence) {
33    for (let i = 0; i < targetN - stampN + 1; i++) {
34      const substring = target.substring(i, i + stampN)
35      if (stampPatterns.has(substring)) {
36        target = target.replace(substring, "?".repeat(stampN))
37        res.unshift(i)
38        continue checkIfAllStamped
39      }
40    }
41
42    // break when no pattern is matched
43    break
44  }
45
46  // double check
47  return target !== beginningSequence ? [] : res
48}