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
class Solution {
 public:
  string findReplaceString(string s, vector<int>& indices,
                           vector<string>& sources, vector<string>& targets) {
    vector<tuple<int, string, string>> operations;

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

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

    for (const auto& [index, source, target] : operations)
      if (string_view(s.data() + 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
class Solution {
  public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    record Operation(int index, String source, String target) {}
    Operation[] operations = new Operation[indices.length];

    for (int i = 0; i < indices.length; ++i)
      operations[i] = new Operation(indices[i], sources[i], targets[i]);

    Arrays.sort(operations, Comparator.comparing(Operation::index, Comparator.reverseOrder())
                                .thenComparing(Operation::source, Comparator.reverseOrder())
                                .thenComparing(Operation::target, Comparator.reverseOrder()));

    for (Operation op : operations)
      if (s.substring(op.index, Math.min(op.index + op.source.length(), s.length()))
              .equals(op.source))
        s = s.substring(0, op.index) + op.target + s.substring(op.index + op.source.length());

    return s;
  }
}

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