Check if an Original String Exists Given Two Encoded Strings - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2060. Check if an Original String Exists Given Two Encoded Strings
Hard
50 Points
String
Dynamic Programming
An original string, consisting of lowercase English letters, can be encoded by the following steps:
For example, one way to encode an original string "abcdefghijklmnop" might be:
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
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'.
Constraints
1 <= s1.length, s2.length <= 40
s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.
The number of consecutive digits in s1 and s2 does not exceed 3.
2060. Check if an Original String Exists Given Two Encoded Strings
Hard
50 Points
String
Dynamic Programming
An original string, consisting of lowercase English letters, can be encoded by the following steps:
For example, one way to encode an original string "abcdefghijklmnop" might be:
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
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'.
Constraints
1 <= s1.length, s2.length <= 40
s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.
The number of consecutive digits in s1 and s2 does not exceed 3.