Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/833.html
833. Find And Replace in String
Level
Medium
Description
To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).
Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.
For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".
Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn’t match x[0] = 'e'.
All these operations occur simultaneously. It’s guaranteed that there won’t be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.
Example 1:
Input: S = “abcd”, indexes = [0,2], sources = [“a”,”cd”], targets = [“eee”,”ffff”]
Output: “eeebffff”
Explanation: “a” starts at index 0 in S, so it’s replaced by “eee”. “cd” starts at index 2 in S, so it’s replaced by “ffff”.
Example 2:
Input: S = “abcd”, indexes = [0,2], sources = [“ab”,”ec”], targets = [“eee”,”ffff”]
Output: “eeecd”
Explanation: “ab” starts at index 0 in S, so it’s replaced by “eee”. “ec” doesn’t starts at index 2 in the original S, so we do nothing.
Notes:
0 <= indexes.length = sources.length = targets.length <= 1000 < indexes[i] < S.length <= 1000- All characters in given inputs are lowercase letters.
Solution
First, for each replacement operation, check whether it is applicable, that is, the string in sources is a substring of S starting at the index in indexes. Use an array occurs of boolean type to store the information, which has the same length as indexes, sources and targets.
Next, create a class IndexSourceTargetOccur to store each replacement operation’s starting index, source word, target word, and applicability. Create an array of type IndexSourceTargetOccur to store each replacement operation. The elements in the array are sorted according to starting indices in ascending order.
Then, use a string buffer to store the original string S, and loop over the array in reversing order, which can make sure that the indices of the substrings in the front part are not changed before replacement operations. For each replacement operation, if it is applicable, then replace the original substring in sources with the new substring in targets.
Finally, convert the string buffer into a string and return.
-
class Solution { public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) { int length = indexes.length; boolean[] occurs = new boolean[length]; for (int i = 0; i < length; i++) { int index = indexes[i]; String source = sources[i]; int curLength = source.length(); occurs[i] = S.substring(index, index + curLength).equals(source); } IndexSourceTargetOccur[] array = new IndexSourceTargetOccur[length]; for (int i = 0; i < length; i++) array[i] = new IndexSourceTargetOccur(indexes[i], sources[i], targets[i], occurs[i]); Arrays.sort(array); StringBuffer sb = new StringBuffer(S); for (int i = length - 1; i >= 0; i--) { IndexSourceTargetOccur indexSourceTargetOccur = array[i]; if (indexSourceTargetOccur.occur) { int index = indexSourceTargetOccur.index; String source = indexSourceTargetOccur.source; String target = indexSourceTargetOccur.target; sb.delete(index, index + source.length()); sb.insert(index, target); } } return sb.toString(); } } class IndexSourceTargetOccur implements Comparable<IndexSourceTargetOccur> { int index; String source; String target; boolean occur; public IndexSourceTargetOccur(int index, String source, String target, boolean occur) { this.index = index; this.source = source; this.target = target; this.occur = occur; } public int compareTo(IndexSourceTargetOccur indexSourceTargetOccur2) { return this.index - indexSourceTargetOccur2.index; } } -
class Solution(object): def findReplaceString(self, S, indexes, sources, targets): """ :type S: str :type indexes: List[int] :type sources: List[str] :type targets: List[str] :rtype: str """ ans = "" i = 0 while i < len(S): if i not in indexes: ans += S[i] i += 1 else: ind = indexes.index(i) source = sources[ind] target = targets[ind] part = S[i : i + len(source)] if part == source: ans += target else: ans += part i += len(source) return ans -
class Solution { public: string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) { int n = s.size(); vector<int> d(n, -1); for (int i = 0; i < indices.size(); ++i) { int j = indices[i]; string source = sources[i]; if (s.substr(j, source.size()) == source) { d[j] = i; } } string ans; for (int i = 0; i < n;) { if (d[i] >= 0) { ans += targets[d[i]]; i += sources[d[i]].size(); } else { ans += s[i++]; } } return ans; } }; -
func findReplaceString(s string, indices []int, sources []string, targets []string) string { n := len(s) d := make([]int, n) for i, j := range indices { source := sources[i] if s[j:min(j+len(source), n)] == source { d[j] = i + 1 } } ans := &strings.Builder{} for i := 0; i < n; { if d[i] > 0 { ans.WriteString(targets[d[i]-1]) i += len(sources[d[i]-1]) } else { ans.WriteByte(s[i]) i++ } } return ans.String() } func min(a, b int) int { if a < b { return a } return b } -
function findReplaceString( s: string, indices: number[], sources: string[], targets: string[], ): string { const n = s.length; const d: number[] = Array(n).fill(-1); for (let k = 0; k < indices.length; ++k) { const [i, src] = [indices[k], sources[k]]; if (s.startsWith(src, i)) { d[i] = k; } } const ans: string[] = []; for (let i = 0; i < n; ) { if (d[i] >= 0) { ans.push(targets[d[i]]); i += sources[d[i]].length; } else { ans.push(s[i++]); } } return ans.join(''); }