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:
["ab", "cdefghijklmn", "o", "p"].["ab", "12", "1", "p"]."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 <= 40s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.s1 and s2 does not exceed 3.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.
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.
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.
Python
JavaScript
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 (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.
The C++ code uses a DP table with dimensions (s1.length + 1) x (s2.length + 1), where each state dp[i][j] represents if the first i characters of s1 can match with the first j characters of s2. We iterate through both strings, updating the DP table by interpreting substrings of digits into numbers and ensuring correct passages through the encoded characters.
Time Complexity: O(n * m). Space Complexity: O(n * m) where n and m are lengths of s1 and s2.
TypeScript
| 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 | — |
| 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 |
Leetcode 2060 - Facebook Interview Question • DailyLeetcode • 3,116 views views
Watch 4 more video solutions →Practice Check if an Original String Exists Given Two Encoded Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor