Show problems as
Classic problem #833MediumArrayHash TableStringSorting

Find And Replace in String

Real-world version: Patching a Label in One Pass
Tracked in this browser only
Read Find And Replace in String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A label reads s. A batch of patches is described by three lists of the same length: patch i targets position indices[i] of the label, looks for the text sources[i] starting exactly there, and if it finds it, replaces that text with targets[i].

A patch whose sources[i] does not appear at that exact position is discarded. Every patch is judged against the original label, never against the result of another patch, and the targeted stretches of two patches never overlap.

Return the label after every surviving patch is applied.

Examples

Example 1

Input
s = "abcdef", indices = [0, 4], sources = ["ab", "ef"], targets = ["wx", "yz"]
Output
"wxcdyz"

Both patches find their text where they expect it, so "ab" at position 0 becomes "wx" and "ef" at position 4 becomes "yz", leaving "cd" untouched.

Example 2

Input
s = "abcdef", indices = [0, 4], sources = ["ab", "gg"], targets = ["wx", "yz"]
Output
"wxcdef"

Position 4 holds "ef", not "gg", so that patch is discarded and only the first one is applied.

Example 3

Input
s = "abab", indices = [0, 2], sources = ["ab", "ba"], targets = ["q", "r"]
Output
"qab"

Position 0 holds "ab" so it becomes "q". Position 2 holds "ab", not "ba", so that patch is discarded.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= indices.length <= 100
  • indices.length == sources.length
  • indices.length == targets.length
  • 0 <= indices[i] <= 999
  • 1 <= sources[i].length <= 50
  • 1 <= targets[i].length <= 50
  • s consists of lowercase English letters only
  • sources[i] and targets[i] consist of lowercase English letters only
  • Every index is inside s, and the stretches two patches target never overlap

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def patch_label(s: str, indices: list[int], sources: list[str], targets: list[str]) -> str:
Java
public String patchLabel(String s, int[] indices, String[] sources, String[] targets)

More on the same topics