#2060
Check if an Original String Exists Given Two Encoded Strings
master · 1640 · lc hard +32 · verified · 43.5% accepted · 327 likes · top 25%
Description
A string is encoded by splitting it into substrings, optionally replacing some substrings with their lengths (as digit strings), then concatenating. Two encoded strings s1 and s2 (containing lowercase letters and digits 1–9) are given. Return true if some original plaintext string could decode to both s1 and s2, otherwise return false. Consecutive digit runs in either input are at most 3 digits long.
Example 1:
Input: s1 = "internationalization", s2 = "i18n"
Output: true
Explanation: It is possible that "internationalization" was the original string.
- "internationalization"
-> Split: ["internationalization"]
-> Do not replace any element
-> Concatenate: "internationalization", which is s1.
- "internationalization"
-> Split: ["i", "nternationalizatio", "n"]
-> Replace: ["i", "18", "n"]
-> Concatenate: "i18n", which is s2
Example 2:
Input: s1 = "l123e", s2 = "44"
Output: true
Explanation: It is possible that "leetcode" was the original string.
- "leetcode"
-> Split: ["l", "e", "et", "cod", "e"]
-> Replace: ["l", "1", "2", "3", "e"]
-> Concatenate: "l123e", which is s1.
- "leetcode"
-> Split: ["leet", "code"]
-> Replace: ["4", "4"]
-> Concatenate: "44", which is s2.
Example 3:
Input: s1 = "a5b", s2 = "c5b"
Output: false
Explanation: It is impossible.
- The original string encoded as s1 must start with the letter 'a'.
- The original string encoded as s2 must start with the letter 'c'.
Code
1
2
3