Check if an Original String Exists Given Two Encoded Strings

Problem

An original string, consisting of lowercase English letters, can be encoded by the following steps:

Arbitrarily split it into a sequence of some number of non-empty substrings.
Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string).
Concatenate the sequence as the encoded string.

For example, one way to encode an original string "abcdefghijklmnop" might be:

Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"].
Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"].
Concatenate the elements of the sequence to get the encoded string: "ab121p".

Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

Examples

Input: s1 = "internationalization", s2 = "i18n"

Output: true

It is possible that 'internationalization' was the original string. s1 keeps the full string unchanged, while s2 splits it as ['i', 'nternationalizatio', 'n'] and replaces the middle part with its length '18'.

Input: s1 = "l123e", s2 = "44"

Output: true

It is possible that 'leetcode' was the original string. s1 encodes it as ['l', '1', '2', '3', 'e'] and s2 encodes it as ['4', '4'] (two groups of 4 characters each).

Input: s1 = "a5b", s2 = "c5b"

Output: false

The original string encoded as s1 must start with 'a', but the original string encoded as s2 must start with 'c'. These are incompatible.

Check if an Original String Exists Given Two Encoded Strings

Problem

Constraints

Examples