Skip to content

833. Find And Replace in String

  • Time: $O(n\log n + n|\texttt{s}|)$, where $n = |\texttt{indices}|$
  • Space: $O(n + |\texttt{s}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  string findReplaceString(string s, vector<int>& indices,
                           vector<string>& sources, vector<string>& targets) {
    vector<pair<int, int>> sortedIndices;

    for (int i = 0; i < indices.size(); ++i)
      sortedIndices.emplace_back(indices[i], i);

    ranges::sort(sortedIndices, greater<>());

    for (const auto& [index, i] : sortedIndices) {
      const string& source = sources[i];
      const string& target = targets[i];
      if (s.substr(index, source.length()) == source)
        s = s.substr(0, index) + target + s.substr(index + source.length());
    }

    return s;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    List<Pair<Integer, Integer>> sortedIndices = new ArrayList<>();

    for (int i = 0; i < indices.length; ++i)
      sortedIndices.add(new Pair<>(indices[i], i));

    Collections.sort(sortedIndices, (a, b) -> b.getKey().compareTo(a.getKey()));

    for (Pair<Integer, Integer> sortedIndex : sortedIndices) {
      final int index = sortedIndex.getKey();
      final int i = sortedIndex.getValue();
      final String source = sources[i];
      final String target = targets[i];
      if (s.substring(index, index + source.length()).equals(source))
        s = s.substring(0, index) + target + s.substring(index + source.length());
    }

    return s;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def findReplaceString(self, s: str, indexes: list[int],
                        sources: list[str], targets: list[str]) -> str:
    for index, source, target in sorted(
            zip(indexes, sources, targets),
            reverse=True):
      if s[index:index + len(source)] == source:
        s = s[:index] + target + s[index + len(source):]
    return s