833. Find And Replace in String

Description

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the ith replacement operation:

1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

• For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

 

Constraints:

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indexes[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s consists of only lowercase English letters.
• sources[i] and targets[i] consist of only lowercase English letters.

Solutions

Solution 1: Simulation

We iterate through each replacement operation. For the current \(k\)-th replacement operation \((i, \text{src})\), if \(s[i..i+|\text{src}|-1]\) is equal to \(\text{src}\), we record that the string at index \(i\) needs to be replaced with the \(k\)-th string in \(\text{targets}\); otherwise, no replacement is needed.

Next, we only need to iterate through the original string \(s\) and perform the replacements based on the recorded information.

The time complexity is \(O(L)\), and the space complexity is \(O(n)\), where \(L\) is the sum of the lengths of all strings, and \(n\) is the length of the string \(s\).

Python3JavaC++GoTypeScript

class Solution:
    def findReplaceString(
        self, s: str, indices: List[int], sources: List[str], targets: List[str]
    ) -> str:
        n = len(s)
        d = [-1] * n
        for k, (i, src) in enumerate(zip(indices, sources)):
            if s.startswith(src, i):
                d[i] = k
        ans = []
        i = 0
        while i < n:
            if ~d[i]:
                ans.append(targets[d[i]])
                i += len(sources[d[i]])
            else:
                ans.append(s[i])
                i += 1
        return "".join(ans)

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length();
        var d = new int[n];
        Arrays.fill(d, -1);
        for (int k = 0; k < indices.length; ++k) {
            int i = indices[k];
            if (s.startsWith(sources[k], i)) {
                d[i] = k;
            }
        }
        var ans = new StringBuilder();
        for (int i = 0; i < n;) {
            if (d[i] >= 0) {
                ans.append(targets[d[i]]);
                i += sources[d[i]].length();
            } else {
                ans.append(s.charAt(i++));
            }
        }
        return ans.toString();
    }
}

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 k = 0; k < indices.size(); ++k) {
            int i = indices[k];
            if (s.compare(i, sources[k].size(), sources[k]) == 0) {
                d[i] = k;
            }
        }
        string ans;
        for (int i = 0; i < n;) {
            if (~d[i]) {
                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 k, i := range indices {
        if strings.HasPrefix(s[i:], sources[k]) {
            d[i] = k + 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()
}

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('');
}

Comments