LeetCode Solutions

			

class Solution {
 public:
  vector<int> movesToStamp(string stamp, string target) {
    vector<int> ans;
    // stamped[i] := true if we already stamped target by stamp on index i
    vector<bool> stamped(target.length());
    int stampedCount = 0;  // Out goal is to make stampedCount = target.length()

    while (stampedCount < target.length()) {
      bool isStamped = false;
      // Try to stamp target[i..i + stamp.length()) for each index
      for (int i = 0; i <= target.length() - stamp.length(); ++i) {
        if (stamped[i])
          continue;
        const int stampified = stampify(stamp, target, i);
        if (stampified == 0)
          continue;
        stampedCount += stampified;
        isStamped = true;
        stamped[i] = true;
        ans.push_back(i);
      }
      // After trying stamp each index, we can't find a valid stamp
      if (!isStamped)
        return {};
    }

    reverse(begin(ans), end(ans));
    return ans;
  }

 private:
  // Stamp target[i..i + stamp.length()) and return # of newly stamped chars
  // E.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***"
  int stampify(const string& stamp, string& target, int s) {
    int stampified = stamp.length();

    for (int i = 0; i < stamp.length(); ++i)
      if (target[s + i] == '*')  // Already stamped
        --stampified;
      else if (target[s + i] != stamp[i])
        return 0;  // We can't stamp on index i

    if (stampified > 0)
      fill(begin(target) + s, begin(target) + s + stamp.length(), '*');

    return stampified;
  }
};

			

class Solution {
  public int[] movesToStamp(String stamp, String target) {
    List<Integer> ans = new ArrayList<>();
    char[] T = target.toCharArray();
    // stamped[i] := true if we already stamped target by stamp on index i
    boolean[] stamped = new boolean[target.length()];
    int stampedCount = 0; // Out goal is to make stampedCount = target.length()

    while (stampedCount < T.length) {
      boolean isStamped = false;
      // Try to stamp target[i..i + stamp.length()) for each index
      for (int i = 0; i <= T.length - stamp.length(); ++i) {
        if (stamped[i])
          continue;
        final int stampified = stampify(stamp, T, i);
        if (stampified == 0)
          continue;
        stampedCount += stampified;
        isStamped = true;
        stamped[i] = true;
        ans.add(i);
      }
      // After trying stamp each index, we can't find a valid stamp
      if (!isStamped)
        return new int[] {};
    }

    Collections.reverse(ans);
    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  // Stamp target[i..i + stamp.length()) and return # of newly stamped chars
  // E.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***"
  private int stampify(final String stamp, char[] T, int s) {
    int stampified = stamp.length();

    for (int i = 0; i < stamp.length(); ++i)
      if (T[s + i] == '*') // Already stamped
        --stampified;
      else if (T[s + i] != stamp.charAt(i))
        return 0; // We can't stamp on index i

    Arrays.fill(T, s, s + stamp.length(), '*');

    return stampified;
  }
}

			

class Solution:
  def movesToStamp(self, stamp: str, target: str) -> List[int]:
    def stampify(s: int) -> int:
      stampified = len(stamp)

      for i, st in enumerate(stamp):
        if target[s + i] == '*':
          stampified -= 1
        elif target[s + i] != st:
          return 0

      for i in range(s, s + len(stamp)):
        target[i] = '*'

      return stampified

    ans = []
    target = list(target)
    stamped = [False] * len(target)
    stampedCount = 0

    while stampedCount < len(target):
      isStamped = False
      for i in range(len(target) - len(stamp) + 1):
        if stamped[i]:
          continue
        stampified = stampify(i)
        if stampified == 0:
          continue
        stampedCount += stampified
        isStamped = True
        stamped[i] = True
        ans.append(i)
      if not isStamped:
        return []

    return ans[::-1]