Check if an Original String Exists Given Two Encoded Strings - Video Solutions
【每日一题】LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings
Check if an Original String Exists Given Two Encoded Strings - Video Solution
Watch 4 video solutions for Check if an Original String Exists Given Two Encoded Strings, a hard level problem involving String, Dynamic Programming. This walkthrough by Huifeng Guan has 2,665 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |