Does the String Fit the Letter Template

Medium

You get a template template and a string text. The string fits the template if every letter of the template can be assigned a non-empty piece of text so that: - the same letter always stands for the same piece; - different letters get different pieces; - replacing each letter of the template with its piece yields exactly text. Return true if text fits template, and false otherwise.

Example 1

template="xyx", text="tictactic" → True

x → "tic", y → "tac" gives tic + tac + tic.

Example 2

template="ab", text="gogo" → True

Four letters split into two pieces as g|ogo, go|go or gog|o. The middle split would give both letters the same piece "go", which is not allowed, but the other two work. The answer is true.

Example 3

template="aab", text="redbluered" → False

Constraints

1 ≤ len(template), len(text) ≤ 20
template and text consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Backtracking

Similar problems

Keypad Words Medium Palindromes From a Set of Letters Medium Next Time From the Same Digits Medium Count the Tile Sequences Medium Every Rewording of a Sentence Medium

Input

template="xyx", text="tictactic"

Expected

True

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