Find And Replace in String 字符串中的查找與替換

問題描述：

你會得到一個字符串 s (索引從 0 開始)，你必須對它執行 k 個替換操作。替換操作以三個長度均為 k 的并行數組給出：indices, sources, targets。

要完成第 i 個替換操作:

1. 檢查 子字符串 sources[i] 是否出現在 原字符串 s 的索引 indices[i] 處。
2. 如果沒有出現， 什么也不做 。
3. 如果出現，則用 targets[i] 替換 該子字符串。

例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替換的結果將是 "eeecd" 。

所有替換操作必須 同時 發生，這意味著替換操作不應該影響彼此的索引。測試用例保證元素間不會重疊 。

• 例如，一個 s = "abc" ， indices = [0,1] ， sources = ["ab"，"bc"] 的測試用例將不會生成，因為 "ab" 和 "bc" 替換重疊。

在對 s 執行所有替換操作后返回 結果字符串 。

子字符串 是字符串中連續的字符序列。

$$\begin{gathered} 1<=s.length<=1000 \\ k==indices.length==sources.length==targets.length \\ 1<=k<=100 \\ 0<=indices[i]<s.length \\ 1<=sources[i].length,targets[i].length<=50 \\ s僅由小寫英文字母組成 \\ sources[i]和targets[i]僅由小寫英文字母組成 \end{gathered}$$

分析

之前的是基于有序的狀態下，依次遍歷每個被操作的字符串的每個位置，所以需要預處理排序。

而線性的思路，與其說是不排序，不如理解為利用數組的自己的有序性 ,避免了排序。

思路

其主要的思路是構建一個長度與原字符串等長的標記數組，然后遍歷每個被操作的索引，并且進行驗證。

• 如果需要替換，那么就把需要替換的目標串放入，并且記錄其影響的位置長度。

• 如果不需要替換，同樣進行標記，該位置的字符串默認直接插入結果串。

需要注意的是在發生替換的情況下，可能會對后續的一定長度的字符跳過。

代碼

線性模擬

class Solution {public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {int n = s.length();var replaceStr = new String[n]; // 替換后的字符串var replaceLen = new int[n];    // 被替換的長度Arrays.fill(replaceLen, 1);     // 無需替換時 i+=1for (int i = 0; i < indices.length; i++) {int idx = indices[i];if (s.startsWith(sources[i], idx)) {replaceStr[idx] = targets[i];replaceLen[idx] = sources[i].length();}}var ans = new StringBuilder();for (int i = 0; i < n; i += replaceLen[i]) { // 無需替換時 i+=1if (replaceStr[i] == null) {ans.append(s.charAt(i));} else {ans.append(replaceStr[i]);}}return ans.toString();}
} 

時間復雜度$O(L)$

空間復雜度$O(L)$

線性代碼來源于靈神大佬

Tag

Array

Sort

String