Check if an Original String Exists Given Two Encoded Strings

An original string is encoded by replacing some non-empty substrings with their lengths. Check if an Original String Exists Given Two Encoded Strings An original string is encoded by replacing some non-empty substrings with their lengths. SWE string dp recursion hard Frequency Single report Last asked 2025-12-09 Stage phone-screen · onsite-coding Check if an Original String Exists Given Two Encoded Strings Problem Description Imagine we have an original string. We encode it by hiding some parts and replacing them with numbers representing their length. You are given two of these encoded strings, s1 and s2. They contain lowercase letters and digits from 1 to 9. The digits tell us how many characters are hidden. However, when digits appear next to each other, it can get tricky. You can interpret consecutive digits as one single number or as a sequence of smaller numbers. For example, the string "123" could mean: One hidden segment of length 123. A segment of length 12 followed by a segment of length 3. A segment of length 1 followed by a segment of length 23. Three separate segments of lengths 1, 2, and 3. Your goal is to check if s1 and s2 could both describe the same original string. Return true if this is possible. Otherwise, return false. Sample Cases Case 1: Input: s1 = "internationalization", s2 = "i18n" Output: true Case 2: Input: s1 = "l123e", s2 = "44" Output: true Case 3: Input: s1 = "a5b", s2 = "c5b" Output: false Input Constraints The lengths of s1 and s2 are between 1 and 40 characters. s1 and s2 only contain lowercase letters and digits 1-9. You will never see more than 3 digits in a row.