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}$$

分析

模擬類型的問題

直接的想法就是依次遍歷，遇到一個索引，進行比較，如果于$source[i]$相同，就要替換成為$t[i]$.

當遇到索引$idx=ind[i]$，$ls=source[i].length$.即$s[idx:idx+ls?1]==source[i]$是否相等。

• 如果相等，$s[idx:idx+ls?1]$就需要被替換。因為有限制，所以不會出現重疊的現象。此時$s[idx+ls]$就是未被替換的字符位置，它和下一個待比較的索引位置的關系一定是 $idx+ls<=nextidx$.

所以在2個待比較的索引之間未被替換的字符串的長度是>=0,這一部分就需要加入到結果中。

• 如果不相等，那么$s[idx:nextidx?1]$的字符串就會全部加入結果中。

模擬

這個思路是以待比較的索引從小到大的排列，并且以索引數組為遍歷目標，進行模擬。

因此需要對原始的三個數組，進行預處理，即進行索引排序。

代碼

排序模擬

class Solution {public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {StringBuilder sb = new StringBuilder();char[] arr = s.toCharArray();int n = indices.length;int len = arr.length;Integer[] indarr = new Integer[n];for(int i=0;i<n;i++) indarr[i] =i;Arrays.sort(indarr,(a,b)->{return indices[a]-indices[b];});int end = 0;for(int i=0;i<n;i++){int idx = indices[indarr[i]];String s1 = sources[indarr[i]];String t1 = targets[indarr[i]];int l1 = s1.length(); if(check(idx,arr,s1)){if(end<idx){ sb.append(s.substring(end,idx));} sb.append(t1);end = idx+l1;}else{int nx = i+1<n?indices[indarr[i+1]]:len;if(idx==nx) continue; sb.append(s.substring(end,idx));sb.append(s.substring(idx,nx));end = nx;} } if(end<len)sb.append(s.substring(end,len));return sb.toString();}public boolean check(int idx,char[] arr,String s){int ls = s.length(),n = arr.length;int l1 = n-idx; if(l1<ls) return false;int ind =0;for(int i = idx;i<idx+ls;i++,ind++){             if(arr[i]!=s.charAt(ind)) return false;  }return true;  }
}

時間復雜度$O(N+MlogM)$

空間復雜度$O(N+ML)$

還有一種線性的思路，S的長度是N，那么就有可能會在N個位置上進行替換操作。有空再寫

Tag

Array

Sort

String