LeetCode 解題筆記：833. Find And Replace in String

作者：王一哲
日期：2026年10月21日


LeetCode 題目連結：833. Find And Replace in String

解題想法

中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 1000)$ 的字串 $s$，1 個長度為 $k$ 的整數陣列 $indices$，2 個長度皆為 $k$ 的字串陣列 $sources$、$targets$。如果 $s$ 於索引值 $sources[i]$ 開始的子字串等於 $target[i]$，則這個子字串會被取代為 $targets[i]$。所有的操作會同時被執行，因此不會有任意 2 個操作影響的範圍重疊。這點很重要，如果需要檢查操作範圍是否重疊，程式寫起來會比較複雜。

我的作法是開一個長度為 $n$ 的陣列 $change$，記錄影響 $s[i]$ 的操作編號，$-1$ 代表無，只標示在開頭。用一個 for 迴圈檢查所有的操作，假設 $idx = indices[i], src = sources[i]$，如果子字串 $s[idx : idx + len(src)] == src$，則 $change[idx] = i$。接下來再用一個 while 迴圈，從索引值 $head = 0$ 開始組合答案 $ans$，如果 $change[head] == -1$，直接將 $s[head]$ 加到 $ans$，再將 $head += 1$；反之，將 $targets[change[head]]$ 加到 $ans$，再將 $head += len(sources[ch])$。

Python 程式碼

寫錯的版本，有檢查操作範圍是否重疊。Runtime: 2 ms, beats 22.30%. Memory: 19.43 MB, beats 15.01%.

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        n = len(s)  # 字串長度
        change = [[] for _ in range(n)]  # 影響 s[i] 的改變編號
        # 檢查 indices, sources 是否作用於 s[j]
        for i, (idx, src) in enumerate(zip(indices, sources)):
            d = len(src)
            if s[idx : idx + d] == src:
                for j in range(idx, idx + d):
                    change[j].append(i)
        
        # 找出有效的操作，作用範圍重疊的操作無效，但其實題目保證不會有這種狀況
        m = len(indices)
        valid = [True] * m
        for ch in change:
            if len(ch) > 1:
                for i in ch:
                    valid[i] = False
        
        # 組合答案
        ans = ""
        head = 0
        while head < n:
            ch = change[head]
            if not ch or not valid[ch[0]]:
                ans += s[head]
                head += 1
            else:
                ans += targets[ch[0]]
                head += len(sources[ch[0]])
        return ans

Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 81.90%.

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        n, m = len(s), len(indices)  # 字串長度，操作數量
        change = [-1] * n  # 影響 s[i] 的操作編號，-1 代表無，只標示在開頭
        # 檢查 indices, sources 是否作用於 s[idx]
        for i in range(m):
            idx = indices[i]
            src = sources[i]
            d = len(src)
            if s[idx : idx + d] == src:
                change[idx] = i
        
        # 組合答案
        ans = []
        head = 0
        while head < n:
            ch = change[head]
            if ch == -1:
                ans.append(s[head])
                head += 1
            else:
                ans.append(targets[ch])
                head += len(sources[ch])
        return "".join(ans)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 14.03 MB, beats 60.22%.

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = (int)s.size(), m = (int)indices.size();  // 字串長度，操作數量
        vector<int> change (n, -1);  // 影響 s[i] 的操作編號，-1 代表無，只標示在開頭
        // 檢查 indices, sources 是否作用於 s[idx]
        for(int i = 0; i < m; i++) {
            string src = sources[i];
            int idx = indices[i], d = (int)src.size();
            if (s.substr(idx, d) == src) {
                change[idx] = i;
            }
        }
        
        // 組合答案
        string ans; 
        int head = 0;
        while(head < n) {
            int ch = change[head];
            if (ch == -1) {
                ans += s[head];
                head++;
            } else {
                ans += targets[ch];
                head += (int)sources[ch].size();
            }
        }
        return ans;
    }
};