Check if an Original String Exists Given Two Encoded Strings solution and explanation
3 more videos on this problem
【每日一题】LeetCode 2060. Check if an Original String Exists Given Two Encoded StringsHuifeng Guan · 44:48 · 2K views
2060. Check if an Original String Exists Given Two Encoded Strings (Leetcode Hard)Programming Live with Larry · 56:14 · 2K views
2060. Check if an Original String Exists Given Two Encoded StringsJust Coding, with Jie · 24:25 · 822 views
LeetCode 2060: Check if an Original String Exists Given Two Encoded StringsAlitaCode · 33:22 · 13 views
The problem
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.
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 <= 40s1ands2consist of digits1-9(inclusive), and lowercase English letters only.- The number of consecutive digits in
s1ands2does not exceed3.
Approach overview
Problem Overview: Two strings contain lowercase letters and digits. Digits represent the length of skipped characters in the original string. The task is to determine whether both encoded strings could decode to the same original string.
Approach 1: Backtracking with Two-Pointers (State Difference Tracking) (Time: O(n * m * D), Space: O(n * m * D))
Traverse both encoded strings using two pointers. Maintain a diff value representing the difference between how many characters each string still needs to match from numeric expansions. When encountering digits, parse all possible numeric combinations (e.g., "12" could mean 1+2 or 12) and update diff. If diff > 0, the first string has unmatched characters; if diff < 0, the second string does. When both pointers point to letters and diff == 0, the letters must match. Use recursion with memoization on (i, j, diff) to avoid recomputation. This approach naturally models the decoding process and works well with pruning.
Approach 2: Dynamic Programming with State Compression (Time: O(n * m * D), Space: O(n * m * D))
Use dynamic programming where the state dp[i][j] stores a set of possible diff values after processing prefixes of both strings. The diff represents the same pending length difference as in the backtracking approach. When digits appear, expand them into all valid numeric values and update the difference. When letters appear, match them directly if diff == 0, or consume pending difference if one side still represents skipped characters. State compression limits the difference range (typically around -1000 to 1000), keeping the DP manageable. This iterative version avoids recursion and systematically explores all valid states.
Both approaches rely heavily on parsing digit sequences and tracking how many characters each encoded string represents without explicitly reconstructing the original string.
Recommended for interviews: Backtracking with memoization is the most commonly discussed solution. It clearly models the decoding process and demonstrates strong understanding of string parsing and backtracking. The DP state compression variant shows deeper mastery of dynamic programming and is useful when interviewers want an iterative formulation.
Approach 1: Backtracking with Two-Pointers
This approach uses two pointers to iterate through the encoded strings s1 and s2. For each character, we check whether it is a letter or a digit. If it's a letter, both strings must match directly at that position. If it's a digit, we use it to determine how many characters we can skip in the original string the encoded version represents. If the two strings can be navigated successfully considering these rules, then the original string can be encoded to both, otherwise, it cannot be.
def is_match(s1, s2):
def backtrack(i, j, p1, p2):
if i == len(s1) and j == len(s2):
return p1 == p2
if i < len(s1) and s1[i].isdigit():
number = 0
while i < len(s1) and s1[i].isdigit():
number = number * 10 + int(s1[i])
i += 1
return backtrack(i, j, p1 + number, p2)
if j < len(s2) and s2[j].isdigit():
number = 0
while j < len(s2) and s2[j].isdigit():
number = number * 10 + int(s2[j])
j += 1
return backtrack(i, j, p1, p2 + number)
if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
return backtrack(i + 1, j + 1, p1 + 1, p2 + 1)
return False
return backtrack(0, 0, 0, 0)function isMatch(s1, s2) {
function backtrack(i, j, p1, p2) {
if (i === s1.length && j === s2.length) return p1 === p2;
if (i < s1.length && !isNaN(s1[i])) {
let number = 0;
while (i < s1.length && !isNaN(s1[i])) {
number = number * 10 + parseInt(s1[i], 10);
i++;
}
return backtrack(i, j, p1 + number, p2);
}
if (j < s2.length && !isNaN(s2[j])) {
let number = 0;
while (j < s2.length && !isNaN(s2[j])) {
number = number * 10 + parseInt(s2[j], 10);
j++;
}
return backtrack(i, j, p1, p2 + number);
}
if (i < s1.length && j < s2.length && s1[i] === s2[j]) {
return backtrack(i + 1, j + 1, p1 + 1, p2 + 1);
}
return false;
}
return backtrack(0, 0, 0, 0);
}The Python code employs a recursive backtracking function backtrack with indices i and j iterating through s1 and s2 respectively. It also maintains p1 and p2 to track the actual length traversed in the potential common original string. When digits are encountered, they are converted into a number and used to jump ahead in the original string's length being tracked. This process continues recursively and returns true if a valid path is found.
Time Complexity: O(n * m) where n and m are the lengths of s1 and s2 respectively in the worst case. Space Complexity: O(n + m) for recursion stack space.
Approach 2: Dynamic Programming with State Compression
Dynamic Programming (DP) is leveraged here to store intermediate results and avoid redundant calculations when matching parts of the strings s1 and s2. The DP table will keep track of whether a specific substring length of 's1' can match a specific substring length of 's2'. The difference lies in using DP instead of backtracking. This method is more memory intensive but can potentially reduce redundant recursive calls.
public class Solution {
public boolean isMatch(String s1, String s2) {
int n = s1.length(), m = s2.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (!dp[i][j]) continue;
int len = 0, num = 0;
for (int k = i; k < n && Character.isDigit(s1.charAt(k)); k++) {
num = num * 10 + (s1.charAt(k) - '0');
len += num;
if (i + len <= n) dp[i + len][j] = true;
}
len = 0; num = 0;
for (int l = j; l < m && Character.isDigit(s2.charAt(l)); l++) {
num = num * 10 + (s2.charAt(l) - '0');
len += num;
if (j + len <= m) dp[i][j + len] = true;
}
if (i < n && j < m && s1.charAt(i) == s2.charAt(j)) {
dp[i + 1][j + 1] = true;
}
}
}
return dp[n][m];
}
}#include <vector>
#include <string>
using namespace std;
bool isMatch(string s1, string s2) {
int n = s1.size(), m = s2.size();
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (!dp[i][j]) continue;
int len = 0, num = 0;
for (int k = i; k < n && isdigit(s1[k]); ++k) {
num = num * 10 + s1[k] - '0';
len += num;
if (i + len <= n) dp[i + len][j] = true;
}
len = 0, num = 0;
for (int l = j; l < m && isdigit(s2[l]); ++l) {
num = num * 10 + s2[l] - '0';
len += num;
if (j + len <= m) dp[i][j + len] = true;
}
if (i < n && j < m && s1[i] == s2[j]) {
dp[i + 1][j + 1] = true;
}
}
}
return dp[n][m];
}The Java implementation also utilizes a dynamic programming approach identical to the C++ version. A 2D boolean DP table is updated with each iteration to track how the possible original string states match between s1 and s2, consolidating stepwise digit interpretations and letter checks.
Time Complexity: O(n * m). Space Complexity: O(n * m) where n and m are lengths of s1 and s2.
Approach 3: Default Approach
function possiblyEquals(s1: string, s2: string): boolean {
const n = s1.length,
m = s2.length;
let dp: Array<Array<Set<number>>> = Array.from({ length: n + 1 }, v =>
Array.from({ length: m + 1 }, w => new Set()),
);
dp[0][0].add(0);
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
for (let delta of dp[i][j]) {
// s1为数字
let num = 0;
if (delta <= 0) {
for (let p = i; i < Math.min(i + 3, n); p++) {
if (isDigit(s1[p])) {
num = num * 10 + Number(s1[p]);
dp[p + 1][j].add(delta + num);
} else {
break;
}
}
}
// s2为数字
num = 0;
if (delta >= 0) {
for (let q = j; q < Math.min(j + 3, m); q++) {
if (isDigit(s2[q])) {
num = num * 10 + Number(s2[q]);
dp[i][q + 1].add(delta - num);
} else {
break;
}
}
}
// 数字匹配s1为字母
if (i < n && delta < 0 && !isDigit(s1[i])) {
dp[i + 1][j].add(delta + 1);
}
// 数字匹配s2为字母
if (j < m && delta > 0 && !isDigit(s2[j])) {
dp[i][j + 1].add(delta - 1);
}
// 两个字母匹配
if (i < n && j < m && delta == 0 && s1[i] == s2[j]) {
dp[i + 1][j + 1].add(0);
}
}
}
}
return dp[n][m].has(0);
}
function isDigit(char: string): boolean {
return /^\d{1}$/g.test(char);
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking with Two-Pointers | Time Complexity: O(n * m) where n and m are the lengths of s1 and s2 respectively in the worst case. Space Complexity: O(n + m) for recursion stack space. |
| Dynamic Programming with State Compression | Time Complexity: O(n * m). Space Complexity: O(n * m) where n and m are lengths of s1 and s2. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Two-Pointers | O(n * m * D) | O(n * m * D) | Interview-friendly solution that models decoding logic clearly |
| Backtracking + Memoization | O(n * m * D) | O(n * m * D) | Prevents repeated state exploration in recursive solutions |
| Dynamic Programming with State Compression | O(n * m * D) | O(n * m * D) | Best when you want an iterative DP formulation without recursion |
Frequently asked questions
Is Check if an Original String Exists Given Two Encoded Strings easy or hard?
The problem is classified as Hard on LeetCode. Handling multiple digit interpretations, managing the difference between expansions, and preventing exponential recursion require strong understanding of dynamic programming and state memoization.
Check if an Original String Exists Given Two Encoded Strings Python/Java solution
Python implementations usually use recursive backtracking with memoization using a dictionary or functools.lru_cache. Java solutions often use DFS with a HashSet for visited states or a DP table storing possible difference values.
How to solve Check if an Original String Exists Given Two Encoded Strings in O(n)?
A strict O(n) solution is not practical because both encoded strings must be explored together. The optimal solutions use either memoized backtracking or dynamic programming with complexity around O(n * m * D), which efficiently handles all valid digit expansions and letter matches.
What is the best approach for Check if an Original String Exists Given Two Encoded Strings?
Backtracking with two pointers and memoization is the most common solution. Track a difference value representing how many characters one encoded string still needs to match relative to the other. Memoizing states (i, j, diff) avoids repeated exploration and keeps the complexity around O(n * m * D).
Is Check if an Original String Exists Given Two Encoded Strings asked at Google/Amazon/Meta?
Hard string and dynamic programming problems like this commonly appear in interviews at companies such as Google, Meta, and Amazon. The problem tests recursive state exploration, memoization, and handling of complex string encoding rules.
What data structure is used in Check if an Original String Exists Given Two Encoded Strings?
Key structures include recursion stacks, hash sets or maps for memoization, and dynamic programming tables. The state typically tracks indices of both strings along with a difference value representing pending unmatched characters.
What is the time complexity of Check if an Original String Exists Given Two Encoded Strings?
The typical complexity is O(n * m * D), where n and m are the lengths of the encoded strings and D is the range of possible difference values (roughly ±1000). Each state represents positions in both strings plus the pending character difference created by numeric expansions.