2060. Check if an Original String Exists Given Two Encoded Strings LeetCode Solution
In this guide, you will get 2060. Check if an Original String Exists Given Two Encoded Strings LeetCode Solution with the best time and space complexity. The solution to Check if an Original String Exists Given Two Encoded Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check if an Original String Exists Given Two Encoded Strings
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.
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.
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.
Complexity Analysis
Time Complexity: O(|\texttt{s1}||\texttt{s1}| \cdot 2000)
Space Complexity: O(|\texttt{s1}||\texttt{s1}| \cdot 2000)
2060. Check if an Original String Exists Given Two Encoded Strings LeetCode Solution in C++
class Solution {
public:
bool possiblyEquals(string s1, string s2) {
vector<vector<unordered_map<int, bool>>> mem(
s1.length() + 1, vector<unordered_map<int, bool>>(s2.length() + 1));
return f(s1, s2, 0, 0, 0, mem);
}
private:
// Returns true if s1[i..n) matches s2[j..n), accounting for the padding
// difference. Here, `paddingDiff` represents the signed padding. A positive
// `paddingDiff` indicates that s1 has an additional number of offset bytes
// compared to s2.
bool f(const string& s1, const string& s2, int i, int j, int paddingDiff,
vector<vector<unordered_map<int, bool>>>& mem) {
if (const auto it = mem[i][j].find(paddingDiff); it != mem[i][j].cend())
return it->second;
if (i == s1.length() && j == s2.length())
return paddingDiff == 0;
if (i < s1.length() && isdigit(s1[i])) {
// Add padding on s1.
const int nextLetterIndex = getNextLetterIndex(s1, i);
for (const int num : getNums(s1.substr(i, nextLetterIndex - i)))
if (f(s1, s2, nextLetterIndex, j, paddingDiff + num, mem))
return true;
} else if (j < s2.length() && isdigit(s2[j])) {
// Add padding on s2.
const int nextLetterIndex = getNextLetterIndex(s2, j);
for (const int num : getNums(s2.substr(j, nextLetterIndex - j)))
if (f(s1, s2, i, nextLetterIndex, paddingDiff - num, mem))
return true;
} else if (paddingDiff > 0) {
// `s1` has more padding, so j needs to catch up.
if (j < s2.length())
return f(s1, s2, i, j + 1, paddingDiff - 1, mem);
} else if (paddingDiff < 0) {
// `s2` has more padding, so i needs to catch up.
if (i < s1.length())
return f(s1, s2, i + 1, j, paddingDiff + 1, mem);
} else { // paddingDiff == 0
// There's no padding difference, so consume the next letter.
if (i < s1.length() && j < s2.length() && s1[i] == s2[j])
return f(s1, s2, i + 1, j + 1, 0, mem);
}
return mem[i][j][paddingDiff] = false;
}
int getNextLetterIndex(const string& s, int i) {
int j = i;
while (i < s.length() && isdigit(s[j]))
++j;
return j;
}
vector<int> getNums(const string& s) {
vector<int> nums{stoi(s)};
if (s.length() == 2) {
nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)));
} else if (s.length() == 3) {
nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 2)));
nums.push_back(stoi(s.substr(0, 2)) + stoi(s.substr(2, 1)));
nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)) +
stoi(s.substr(2, 1)));
}
return nums;
}
}; /* code provided by PROGIEZ */
2060. Check if an Original String Exists Given Two Encoded Strings LeetCode Solution in Java
class Solution {
public boolean possiblyEquals(String s1, String s2) {
Map<Integer, Boolean>[][] mem = new Map[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); ++i)
for (int j = 0; j <= s2.length(); ++j)
mem[i][j] = new HashMap<>();
return f(s1, s2, 0, 0, 0, mem);
}
// Returns true if s1[i..n) matches s2[j..n), accounting for the padding
// difference. Here, `paddingDiff` represents the signed padding. A positive
// `paddingDiff` indicates that s1 has an additional number of offset bytes
// compared to s2.
private boolean f(final String s1, final String s2, int i, int j, int paddingDiff,
Map<Integer, Boolean>[][] mem) {
if (mem[i][j].containsKey(paddingDiff))
return mem[i][j].get(paddingDiff);
if (i == s1.length() && j == s2.length())
return paddingDiff == 0;
if (i < s1.length() && Character.isDigit(s1.charAt(i))) {
// Add padding on s1.
final int nextLetterIndex = getNextLetterIndex(s1, i);
for (final int num : getNums(s1.substring(i, nextLetterIndex)))
if (f(s1, s2, nextLetterIndex, j, paddingDiff + num, mem))
return true;
} else if (j < s2.length() && Character.isDigit(s2.charAt(j))) {
// Add padding on s2.
final int nextLetterIndex = getNextLetterIndex(s2, j);
for (final int num : getNums(s2.substring(j, nextLetterIndex)))
if (f(s1, s2, i, nextLetterIndex, paddingDiff - num, mem))
return true;
} else if (paddingDiff > 0) {
// `s1` has more padding, so j needs to catch up.
if (j < s2.length())
return f(s1, s2, i, j + 1, paddingDiff - 1, mem);
} else if (paddingDiff < 0) {
// `s2` has more padding, so i needs to catch up.
if (i < s1.length())
return f(s1, s2, i + 1, j, paddingDiff + 1, mem);
} else { // paddingDiff == 0
// There's no padding difference, so consume the next letter.
if (i < s1.length() && j < s2.length() && s1.charAt(i) == s2.charAt(j))
return f(s1, s2, i + 1, j + 1, 0, mem);
}
mem[i][j].put(paddingDiff, false);
return false;
}
private int getNextLetterIndex(final String s, int i) {
int j = i;
while (j < s.length() && Character.isDigit(s.charAt(j)))
++j;
return j;
}
private List<Integer> getNums(final String s) {
List<Integer> nums = new ArrayList<>(List.of(Integer.parseInt(s)));
if (s.length() == 2) {
nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)));
} else if (s.length() == 3) {
nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 3)));
nums.add(Integer.parseInt(s.substring(0, 2)) + Integer.parseInt(s.substring(2, 3)));
nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)) +
Integer.parseInt(s.substring(2, 3)));
}
return nums;
}
} // code provided by PROGIEZ
2060. Check if an Original String Exists Given Two Encoded Strings LeetCode Solution in Python
class Solution:
def possiblyEquals(self, s1: str, s2: str) -> bool:
def getNums(s: str) -> set[int]:
nums = {int(s)}
for i in range(1, len(s)):
nums |= {x + y for x in getNums(s[:i]) for y in getNums(s[i:])}
return nums
def getNextLetterIndex(s: str, i: int) -> int:
j = i
while j < len(s) and s[j].isdigit():
j += 1
return j
@functools.lru_cache(None)
def dp(i: int, j: int, paddingDiff: int) -> bool:
"""
Returns True if s1[i..n) matches s2[j..n), accounting for the padding
difference. Here, `paddingDiff` represents the signed padding. A positive
`paddingDiff` indicates that s1 has an additional number of offset bytes
compared to s2.
"""
if i == len(s1) and j == len(s2):
return paddingDiff == 0
# Add padding on s1.
if i < len(s1) and s1[i].isdigit():
nextLetterIndex = getNextLetterIndex(s1, i)
for num in getNums(s1[i:nextLetterIndex]):
if dp(nextLetterIndex, j, paddingDiff + num):
return True
# Add padding on s2.
elif j < len(s2) and s2[j].isdigit():
nextLetterIndex = getNextLetterIndex(s2, j)
for num in getNums(s2[j:nextLetterIndex]):
if dp(i, nextLetterIndex, paddingDiff - num):
return True
# `s1` has more padding, so j needs to catch up.
elif paddingDiff > 0:
if j < len(s2):
return dp(i, j + 1, paddingDiff - 1)
# `s2` has more padding, so i needs to catch up.
elif paddingDiff < 0:
if i < len(s1):
return dp(i + 1, j, paddingDiff + 1)
# There's no padding difference, so consume the next letter.
else: # paddingDiff == 0
if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
return dp(i + 1, j + 1, 0)
return False
return dp(0, 0, 0) # code by PROGIEZ
