Hard · Dynamic Programming

Check if An Original String Exists Given Two Encoded Strings

A lowercase original string is encoded by splitting it into non-empty pieces and replacing any of those pieces with their lengths written in decimal. Given two encoded strings s1 and s2 (lowercase letters and digits 1–9), return true if some original string could be encoded as both, otherwise false.

Examples

Example 1

"l2t" ?= "leet" (true)

Output: true

Example 2

"ab" ?= "a2" (false)

Output: false

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.