Pattern With Allowed Swaps

Hard

You get a string text, a pattern string pattern and a list of rules swaps. A rule swaps[i] = [from, to] means that a character from in the pattern may be replaced with to. Rules only work in one direction. Replacements happen in the pattern, at any number of positions, but each position of the pattern can be replaced at most once (no chains like a → b → c at one position). Return True if, after some replacements (possibly none), the pattern becomes a contiguous piece of text, and False otherwise. Letter case matters.

Example 1

text="unitr2d2ok", pattern="rodo", swaps=[["o", "2"], ["d", "x"]] → True

Replace both o characters of the pattern with 2 to get r2d2, which appears in the text.

Example 2

text="abcde", pattern="xcd", swaps=[["b", "x"]] → False

The rule lets b become x, not the other way round, so the x in the pattern stays x, and no such piece exists in the text.

Example 3

text="Q7Q7", pattern="q7", swaps=[["q", "Q"]] → True

Constraints

1 ≤ len(pattern) ≤ len(text) ≤ 5000
0 ≤ len(swaps) ≤ 1000
swaps[i] = [from, to], from ≠ to
Every character is an English letter (lower or upper case) or a digit

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String String Matching

Similar problems

Highlight Search Hits Medium Highlight Search Terms Medium Every Way to Space the Words Hard Glued Into a Palindrome Hard One-Swap Word Families Hard

Input

text="unitr2d2ok", pattern="rodo", swaps=[["o", "2"], ["d", "x"]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.