# Check if an Original String Exists Given Two Encoded Strings **Difficulty:** HARD [External](https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings) Canonical: https://scaleengineer.com/dsa/problems/check-if-an-original-string-exists-given-two-encoded-strings **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** String **Companies:** [BitGo](https://scaleengineer.com/companies/bitgo) --- ## 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 <= 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`. # Approaches ## Brute Force Recursion This approach uses a straightforward recursive function to explore all possible ways the two strings `s1` and `s2` could have been generated from a common original string. The state of the recursion is defined by the current positions in both strings and a 'difference' counter. This counter, `diff`, tracks the balance of wildcard characters. A positive `diff` means `s1` is 'ahead' by `diff` characters (which must be matched by `s2`), while a negative `diff` means `s2` is ahead. The function branches out based on the characters at the current positions: matching letters, parsing numbers to update the `diff`, or using the existing `diff` to skip characters. This exhaustive search checks every possibility. **Time:** Exponential, potentially O(3^(N+M)) in the worst case. The branching factor can be large, especially when parsing numbers, leading to a combinatorial explosion of recursive calls. · **Space:** O(N + M), where N and M are the lengths of the strings. This is for the recursion stack depth. **Pros:** Conceptually simple and a direct translation of the problem statement.; Requires minimal data structures. **Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will likely result in a 'Time Limit Exceeded' error for most non-trivial test cases. ### Explanation The core of this approach is a recursive function that simulates the matching process. It does not store the results of its computations, leading to a large number of redundant calls for the same state `(i, j, diff)`. ```java class Solution { public boolean possiblyEquals(String s1, String s2) { return solve(s1, s2, 0, 0, 0); } private boolean solve(String s1, String s2, int i, int j, int diff) { int n1 = s1.length(); int n2 = s2.length(); if (i == n1 && j == n2) { return diff == 0; } // Case 1: s1 has wildcards (diff > 0) if (diff > 0) { if (j < n2 && Character.isLetter(s2.charAt(j))) { if (solve(s1, s2, i, j + 1, diff - 1)) return true; } } // Case 2: s2 has wildcards (diff < 0) else if (diff < 0) { if (i < n1 && Character.isLetter(s1.charAt(i))) { if (solve(s1, s2, i + 1, j, diff + 1)) return true; } } // Case 3: diff == 0, match letters else { // diff == 0 if (i < n1 && j < n2 && Character.isLetter(s1.charAt(i)) && Character.isLetter(s2.charAt(j))) { if (s1.charAt(i) == s2.charAt(j)) { if (solve(s1, s2, i + 1, j + 1, 0)) return true; } } } // Case 4: Parse a number from s1 (possible for any diff) if (i < n1 && Character.isDigit(s1.charAt(i))) { int num = 0; for (int k = i; k < Math.min(i + 3, n1) && Character.isDigit(s1.charAt(k)); k++) { num = num * 10 + (s1.charAt(k) - '0'); if (solve(s1, s2, k + 1, j, diff + num)) return true; } } // Case 5: Parse a number from s2 (possible for any diff) if (j < n2 && Character.isDigit(s2.charAt(j))) { int num = 0; for (int k = j; k < Math.min(j + 3, n2) && Character.isDigit(s2.charAt(k)); k++) { num = num * 10 + (s2.charAt(k) - '0'); if (solve(s1, s2, i, k + 1, diff - num)) return true; } } return false; } } ``` *Note: The logic in this simplified brute-force code is slightly flawed because the cases are not mutually exclusive and should be handled more carefully as in the optimized DP solution. However, it illustrates the basic recursive structure.* ### Algorithm - Define a recursive function `solve(i, j, diff)` where `i` is the index in `s1`, `j` is the index in `s2`, and `diff` is the balance of wildcard characters. - **Base Case:** If both `i` and `j` have reached the end of their respective strings (`i == s1.length()` and `j == s2.length()`), a match is possible if and only if `diff` is zero. Return `diff == 0`. - **Recursive Step:** The function explores all possible valid moves from the current state `(i, j, diff)`: - **If `diff > 0`:** This means `s1` has `diff` wildcards to be matched. We must advance in `s2`. - If `s2[j]` is a letter, we use one wildcard: `solve(i, j + 1, diff - 1)`. - If `s2[j]` is a digit, we parse a number `val` from `s2` and update the balance: `solve(i, j + k, diff - val)`. - **If `diff < 0`:** This means `s2` has `-diff` wildcards. This is symmetric to the previous case; we must advance in `s1`. - If `s1[i]` is a letter: `solve(i + 1, j, diff + 1)`. - If `s1[i]` is a digit: `solve(i + k, j, diff + val)`. - **If `diff == 0`:** The number of characters matched so far is equal. - If `s1[i]` and `s2[j]` are both letters, they must be identical for a match to be possible: `solve(i + 1, j + 1, 0)`. - We can also choose to parse a number from either `s1` or `s2` to create a new wildcard balance. For a number `val` from `s1`, we call `solve(i + k, j, val)`. For a number `val` from `s2`, we call `solve(i, j + k, -val)`. - The function returns `true` if any of these recursive calls return `true`, indicating a valid path was found. Otherwise, it returns `false`. ## Recursion with Memoization (Top-Down Dynamic Programming) The brute-force approach is inefficient because it repeatedly solves the same subproblems. We can significantly optimize this by using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This transforms the exponential time complexity into a polynomial one, effectively implementing a top-down dynamic programming solution. We use a 3D array, `memo[i][j][diff]`, to store the boolean result for the state defined by the current indices `i` in `s1`, `j` in `s2`, and the character balance `diff`. Whenever the recursive function is called with a state that has been computed before, we return the stored result instantly, pruning a large portion of the recursion tree. **Time:** O(N * M * D). Each state `(i, j, diff)` is computed only once. The transitions from each state take constant time (as the number-parsing loop is at most 3 iterations). · **Space:** O(N * M * D), where N and M are the lengths of the strings, and D is the range of possible `diff` values (around 2000). This is for the memoization table. **Pros:** Highly efficient and guaranteed to pass within typical time limits.; Avoids all redundant computations by caching results. **Cons:** Requires a large amount of memory for the 3D memoization table. ### Explanation This approach enhances the brute-force recursion by adding a memoization table to cache the results of subproblems. The state `(i, j, diff)` uniquely identifies a subproblem: can `s1[i:]` and `s2[j:]` match given a wildcard balance of `diff`? ```java class Solution { private Boolean[][][] memo; private String s1; private String s2; private int n1; private int n2; public boolean possiblyEquals(String s1, String s2) { this.s1 = s1; this.s2 = s2; this.n1 = s1.length(); this.n2 = s2.length(); // diff can range from approx -999 to 999. We use an offset of 1000. this.memo = new Boolean[n1 + 1][n2 + 1][2001]; return solve(0, 0, 0); } private boolean solve(int i, int j, int diff) { if (i == n1 && j == n2) { return diff == 0; } if (memo[i][j][diff + 1000] != null) { return memo[i][j][diff + 1000]; } boolean res = false; // Case 1: s1 has wildcards (diff > 0), so we must advance in s2. if (diff > 0) { if (j < n2) { if (Character.isDigit(s2.charAt(j))) { int num = 0; for (int k = j; k < Math.min(j + 3, n2) && Character.isDigit(s2.charAt(k)); k++) { num = num * 10 + (s2.charAt(k) - '0'); if (solve(i, k + 1, diff - num)) { res = true; break; } } } else { // s2[j] is a letter, consume it. if (solve(i, j + 1, diff - 1)) res = true; } } } // Case 2: s2 has wildcards (diff < 0), so we must advance in s1. else if (diff < 0) { if (i < n1) { if (Character.isDigit(s1.charAt(i))) { int num = 0; for (int k = i; k < Math.min(i + 3, n1) && Character.isDigit(s1.charAt(k)); k++) { num = num * 10 + (s1.charAt(k) - '0'); if (solve(k + 1, j, diff + num)) { res = true; break; } } } else { // s1[i] is a letter, consume it. if (solve(i + 1, j, diff + 1)) res = true; } } } // Case 3: diff == 0. We can either match letters or parse new numbers. else { // diff == 0 if (i < n1 && j < n2 && Character.isLetter(s1.charAt(i)) && Character.isLetter(s2.charAt(j))) { if (s1.charAt(i) == s2.charAt(j) && solve(i + 1, j + 1, 0)) { res = true; } } if (!res && i < n1 && Character.isDigit(s1.charAt(i))) { int num = 0; for (int k = i; k < Math.min(i + 3, n1) && Character.isDigit(s1.charAt(k)); k++) { num = num * 10 + (s1.charAt(k) - '0'); if (solve(k + 1, j, num)) { res = true; break; } } } if (!res && j < n2 && Character.isDigit(s2.charAt(j))) { int num = 0; for (int k = j; k < Math.min(j + 3, n2) && Character.isDigit(s2.charAt(k)); k++) { num = num * 10 + (s2.charAt(k) - '0'); if (solve(i, k + 1, -num)) { res = true; break; } } } } return memo[i][j][diff + 1000] = res; } } ``` ### Algorithm - Create a 3D memoization table, `memo[s1.length() + 1][s2.length() + 1][2001]`, to store results for states `(i, j, diff)`. Initialize it to a value indicating 'not computed' (e.g., `null`). The `diff` dimension is offset by 1000 to handle negative values. - Use the same recursive function `solve(i, j, diff)` as in the brute-force approach. - **Memoization Check:** At the beginning of the function, check if `memo[i][j][diff + 1000]` has been computed. If so, return the stored value immediately. - **Recursive Logic:** The logic for transitions remains the same, exploring all possibilities of matching characters, parsing numbers, or consuming wildcards based on the current state. - **Store Result:** Before returning any result (`true` or `false`), store it in `memo[i][j][diff + 1000]` to avoid re-computation.