One Word, Two Shorthands

Hard

A word of lowercase English letters is shortened like this: split it into several consecutive non-empty pieces, replace some of the pieces (possibly none) with their length written in digits, and glue everything back together. For example, abcdefg can be split into ab, cde, f, g, and replacing the second and third pieces gives ab31g. You are given two shorthands first and second made of lowercase English letters and the digits 1 to 9. Return True if some word could produce both of them, and False otherwise. Note that a run of digits is not necessarily a single number: 31 may stand for one piece of length 31 or for two pieces of lengths 3 and 1.

Example 1

first="k8s", second="kuber4es" → False

The word kubernetes fits: k8s replaces the eight letters ubernete with a number, and kuber4es replaces the four letters nete.

Example 2

first="a11", second="2b" → True

11 may be read as two one-letter pieces (1 and 1). Then a word such as axb fits: three letters, starting with a and ending with b.

Example 3

first="ab3", second="2c1" → False

The first shorthand describes a 5-letter word, the second a 4-letter one, so no word fits both.

Constraints

1 ≤ len(first), len(second) ≤ 40
Both strings consist of lowercase English letters and the digits 1 to 9
No more than 3 digits appear in a row

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming