936. 戳印序列

思路

• 蓋章時，會把前面的東西覆蓋掉。
• 如果蓋章可以得到target，那麼target必定包含stamp字串。
• 先蓋的東西如果跟target有不相同之處，就需要用後面的蓋章去取消掉它。

用範例來說，"ababc"能找到"abc"，那麼最後一步肯定是蓋2位置，上一步是"ab???"，此時有一個字串"ab?"跟stamp只差一個字元，而這個字元會被後面覆蓋，因此可以蓋零位置。

有點像時光倒流

再舉個例子，target="aabcbc"，stamp="abc"。

此時最佳位置是第一個，因此最後一步蓋一位置，target="a???bc"
因為會蓋位置一，蓋其他位置的錯誤狀態因此更新。

這時可以蓋零或是三位置，這裡蓋零，target="????bc"，再次更新其他位置的狀態

再蓋第三個位置，target = "??????"，更新狀態。

蓋第二個位置
$\begin{array}{} ? & b & c \\ a & b & c \\ \checkmark & \checkmark & \checkmark \end{array}$

把蓋章的順序倒過來，就得到答案 $[2,3,0,1]$ 了。 整個過程就是在做拓樸排序，入度就是打叉的個數，當入度為 0 時，這個位置就可以蓋章。 剩下的細節，在程式碼當中有註解。

程式碼

1. 拓樸排序 鄰接表

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        // 如果 stamp.size() = 10, target.size() = 9, 那麼一共有兩個位置可以蓋章
        int m = stamp.length();
        int n = target.length();
        int len = n - m + 1; // 可蓋章的位置
        vector<vector<int>> graph(n); // 紀錄鄰居 
        vector<int> indegree(len);
        for(int i = 0; i < len; i++) {
            int cnt = 0;
            for(int j = 0; j < m; j++) {
                if(stamp[j] != target[i + j]) { // 計算不相同之處
                    cnt++;
                    // 當 i+j 的錯誤被修正時，蓋在位置 i 的印章入度會減一（解鎖）
                    graph[i + j].push_back(i);
                }
            }
            indegree[i] = cnt; // 紀錄每個位置蓋章的入度，也就是字串不同的個數
        }
        queue<int> q;
        for(int i = 0; i < len; i++) {
            if(indegree[i] == 0) {
                q.push(i);
            }
        }
        vector<int> res;
        vector<bool> visited(n, false); // 紀錄哪些位置被解鎖了（範例中的標為？），避免重複解鎖
        while(!q.empty()) {
            int top = q.front(); q.pop();
            res.push_back(top); // 印章蓋在 top 位置
            for(int i = 0; i < m; i++) { // 後續長度 m 的位置都會受到影響
                if(!visited[top + i]) {
                    visited[top + i] = true;
                    for(int& neighbor : graph[top + i]) { // 受到影響的地方，入度減一
                        if(--indegree[neighbor] == 0) {
                            q.push(neighbor);
                        }
                    }
                }
            }
        }
        if(res.size() == len && res.size() <= 10 * n) {
            reverse(res.begin(), res.end());
            return res;
        }
        else {
            return {};
        }
    }
};

2. 拓樸排序 鄰接表 簡化

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        // 如果 stamp.size() = 10, target.size() = 9, 那麼一共有兩個位置可以蓋章
        int m = stamp.length();
        int n = target.length();
        int len = n - m + 1; // 可蓋章的位置
        vector<vector<int>> graph(n); // 紀錄鄰居 
        vector<int> indegree(len, m); // 預設最大入度
        queue<int> q;
        for(int i = 0; i < len; i++) {
            int cnt = 0;
            for(int j = 0; j < m; j++) {
                if(stamp[j] == target[i + j]) { // 計算不相同之處
                    if(--indegree[i] == 0) { // 入度為 0，可以當最後蓋印章的位置
                        q.push(i);
                    }
                }
                else {
                    // 當 i+j 的錯誤被修正時，蓋在位置 i 的印章入度會減一（解鎖）
                    graph[i + j].push_back(i);                    
                }
            }
        }
        vector<int> res;
        vector<bool> visited(n, false); // 紀錄哪些位置被解鎖了（範例中的標為？），避免重複解鎖
        while(!q.empty()) {
            int top = q.front(); q.pop();
            res.push_back(top); // 印章蓋在 top 位置
            for(int i = 0; i < m; i++) { // 後續長度 m 的位置都會受到影響
                if(!visited[top + i]) {
                    visited[top + i] = true;
                    for(int& neighbor : graph[top + i]) { // 受到影響的地方，入度減一
                        if(--indegree[neighbor] == 0) {
                            q.push(neighbor);
                        }
                    }
                }
            }
        }
        if(res.size() == len && res.size() <= 10 * n) {
            reverse(res.begin(), res.end());
            return res;
        }
        else {
            return {};
        }
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n\times{m})$