Scale Engineer

Check if an Original String Exists Given Two Encoded Strings

Hard
#1876Time: 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.1 company
Patterns
Dynamic Programming
Data structures
String
Companies
BitGo

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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).

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.

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem