# LeetCode: Stamping The Sequence Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * getAllStampPatterns('abc')3 * => a**, ab*, abc, *b*, *bc, **c4 */5const getAllStampPatterns = stamp => {6  const stampPatterns = new Set() // for O(1) lookup7  const stampN = stamp.length8  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 stampPatterns18}19
20/**21 * @param {string} stamp22 * @param {string} target23 * @return {number[]}24 */25var movesToStamp = function (stamp, target) {26  const targetN = target.length27  const stampN = stamp.length28  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 checkIfAllStamped39      }40    }41
42    // break when no pattern is matched43    break44  }45
46  // double check47  return target !== beginningSequence ? [] : res48}```

leetcode

string

greedy

## Next Post

LeetCode: Russian Doll Envelopes

Mar 31, 2021

Search Posts