Hard

题目描述

给你两个字符串 stamp 和 target。一开始，有一个字符串 s 的长度与 target.length 相同，所有的 s[i] 都是 '?'。

在一次操作中，你可以将 stamp 放在 s 上，并将 s 中的每个字母替换为 stamp 中对应的字母。

例如，如果 stamp = "abc" 和 target = "abcba"，那么 s 最初是 "?????"。在一次操作中你可以：

  • 将戳印放在 s 的索引 0 处得到 "abc??"，
  • 将戳印放在 s 的索引 1 处得到 "?abc?"，或
  • 将戳印放在 s 的索引 2 处得到 "??abc"。

注意 stamp 必须完全包含在 s 的边界内才能进行戳印（即，你不能将 stamp 放在 s 的索引 3 处）。

我们希望使用最多 10 * target.length 次操作将 s 转换为 target。

返回每次戳印时左端字母的索引数组。如果在 10 * target.length 次操作内无法从 s 得到 target，则返回空数组。

示例 1：

输入：stamp = "abc", target = "ababc"
输出：[0,2]
解释：
初始时 s = "?????"。
- 将戳印放在索引 0 处得到 "abc??"。
- 将戳印放在索引 2 处得到 "ababc"。
[1,0,2] 也是可接受的答案，还有一些其他答案。

示例 2：

输入：stamp = "abca", target = "aabcaca"
输出：[3,0,1]
解释：
初始时 s = "???????"。
- 将戳印放在索引 3 处得到 "???abca"。
- 将戳印放在索引 0 处得到 "abcabca"。
- 将戳印放在索引 1 处得到 "aabcaca"。

提示：

  • 1 <= stamp.length <= target.length <= 1000
  • stamp 和 target 仅由小写英文字母组成。

解题思路

这是一个经典的逆向思维问题。关键思路是从结果倒推：不是考虑如何从空白字符串构建目标串，而是考虑如何从目标串倒退回空白字符串。

核心思想：

  1. 逆向操作：将戳印操作看作是"擦除"操作，即找到可以被戳印覆盖的位置，将其变回 ‘?’
  2. 贪心策略：每次找到一个可以被戳印完全匹配的位置（允许部分位置是’?’），将其全部替换为’?'
  3. 重复过程：持续执行上述过程，直到整个目标串都变成’?'

算法步骤：

  1. 从目标字符串开始，寻找所有可以被戳印匹配的位置
  2. 对于每个位置，检查是否可以与戳印匹配（已经是’?‘的位置可以匹配任何字符）
  3. 如果找到匹配位置，将该位置的所有字符替换为’?’，并记录戳印位置
  4. 重复步骤2-3，直到整个字符串都变成’?’
  5. 由于是逆向操作，最后需要反转结果数组

这种方法的时间复杂度是合理的，因为每次操作至少会将一个非’?‘字符变为’?’，最多需要target.length次操作。

代码实现

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        vector<int> result;
        vector<char> targetArr(target.begin(), target.end());
        bool changed = true;
        
        while (changed) {
            changed = false;
            for (int i = 0; i <= (int)target.length() - (int)stamp.length(); i++) {
                if (canStamp(stamp, targetArr, i)) {
                    changed = true;
                    for (int j = 0; j < stamp.length(); j++) {
                        targetArr[i + j] = '?';
                    }
                    result.push_back(i);
                }
            }
        }
        
        for (char c : targetArr) {
            if (c != '?') return {};
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
    
private:
    bool canStamp(const string& stamp, const vector<char>& target, int pos) {
        bool hasNonQuestion = false;
        for (int i = 0; i < stamp.length(); i++) {
            if (target[pos + i] != '?' && target[pos + i] != stamp[i]) {
                return false;
            }
            if (target[pos + i] != '?') {
                hasNonQuestion = true;
            }
        }
        return hasNonQuestion;
    }
};

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        target = list(target)
        result = []
        changed = True
        
        while changed:
            changed = False
            for i in range(len(target) - len(stamp) + 1):
                if self.canStamp(stamp, target, i):
                    changed = True
                    for j in range(len(stamp)):
                        target[i + j] = '?'
                    result.append(i)
        
        if all(c == '?' for c in target):
            return result[::-1]
        else:
            return []
    
    def canStamp(self, stamp, target, pos):
        has_non_question = False
        for i in range(len(stamp)):
            if target[pos + i] != '?' and target[pos + i] != stamp[i]:
                return False
            if target[pos + i] != '?':
                has_non_question = True
        return has_non_question

public class Solution {
    public int[] MovesToStamp(string stamp, string target) {
        var targetArray = target.ToCharArray();
        var result = new List<int>();
        bool changed = true;
        
        while (changed) {
            changed = false;
            for (int i = 0; i <= target.Length - stamp.Length; i++) {
                if (CanStamp(stamp, targetArray, i)) {
                    changed = true;
                    for (int j = 0; j < stamp.Length; j++) {
                        targetArray[i + j] = '?';
                    }
                    result.Add(i);
                }
            }
        }
        
        foreach (char c in targetArray) {
            if (c != '?') return new int[0];
        }
        
        result.Reverse();
        return result.ToArray();
    }
    
    private bool CanStamp(string stamp, char[] target, int pos) {
        bool hasNonQuestion = false;
        for (int i = 0; i < stamp.Length; i++) {
            if (target[pos + i] != '?' && target[pos + i] != stamp[i]) {
                return false;
            }
            if (target[pos + i] != '?') {
                hasNonQuestion = true;
            }
        }
        return hasNonQuestion;
    }
}

var movesToStamp = function(stamp, target) {
    const targetArray = target.split('');
    const result = [];
    let changed = true;
    
    while (changed) {
        changed = false;
        for (let i = 0; i <= target.length - stamp.length; i++) {
            if (canStamp(stamp, targetArray, i)) {
                changed = true;
                for (let j = 0; j < stamp.length; j++) {
                    targetArray[i + j] = '?';
                }
                result.push(i);
            }
        }
    }
    
    for (const c of targetArray) {
        if (c !== '?') return [];
    }
    
    return result.reverse();
};

function canStamp(stamp, target, pos) {
    let hasNonQuestion = false;
    for (let i = 0; i < stamp.length; i++) {
        if (target[pos + i] !== '?' && target[pos + i] !== stamp[i]) {
            return false;
        }
        if (target[pos + i] !== '?') {
            hasNonQuestion = true;
        }
    }
    return hasNonQuestion;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) 其中 n 是 target 的长度。最多需要 n 次外层循环，每次循环检查 O(n) 个位置
空间复杂度O(n) 用于存储目标字符串的字符数组和结果数组