# Check if an Original String Exists Given Two Encoded Strings

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

解题思路：

dfs+memo

* **State Tracking (`diff`)**:
  * `diff` tracks the difference in the length of substrings that have been skipped over due to digit expansions.
  * A positive `diff` means that `s1` is ahead of `s2` by `diff` characters, while a negative `diff` means that `s2` is ahead by `-diff` characters.
* **Digit Handling**:
  * The code carefully handles cases where a digit might represent a sequence of characters by iterating through possible digit lengths.
  * For each possible digit, it tries to match it against the other string's sequence.
* **Character Matching**:
  * When both `s1` and `s2` have characters (not digits) and `diff == 0`, the code attempts to match the characters directly.
* **Recursive Exploration**:
  * The function recursively explores all possible ways to align and match the strings. It returns `True` if a valid match is found, and `False` otherwise.

```
from functools import cache

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i: int, j: int, diff: int) -> bool:
            # When both strings have been processed, check if there is no length difference left
            if i == len(s1) and j == len(s2):
                return diff == 0

            # Explore possible digit expansions in s1
            if i < len(s1) and s1[i].isdigit():
                num = 0
                for k in range(i, len(s1)):
                    if not s1[k].isdigit():
                        break
                    num = num * 10 + int(s1[k])
                    if dfs(k + 1, j, diff - num):
                        return True

            # Explore possible digit expansions in s2
            if j < len(s2) and s2[j].isdigit():
                num = 0
                for k in range(j, len(s2)):
                    if not s2[k].isdigit():
                        break
                    num = num * 10 + int(s2[k])
                    if dfs(i, k + 1, diff + num):
                        return True

            # When diff is 0, and both characters are the same, proceed
            if i < len(s1) and j < len(s2) and diff == 0 and s1[i] == s2[j]:
                return dfs(i + 1, j + 1, diff)

            # Handle cases where diff is not zero
            # If diff > 0, it means s1 has extra characters to match against s2
            if diff > 0 and i < len(s1) and not s1[i].isdigit():
                return dfs(i + 1, j, diff - 1)

            # If diff < 0, it means s2 has extra characters to match against s1
            if diff < 0 and j < len(s2) and not s2[j].isdigit():
                return dfs(i, j + 1, diff + 1)

            return False
        
        return dfs(0, 0, 0)

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/check-if-an-original-string-exists-given-two-encoded-strings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.