Check if an Original String Exists Given Two Encoded Strings — LeetCode 2060 Python Solution

HardStringDynamic Programming

Problem: #2060
Pattern: Dynamic Programming
Reading time: 8 min
Source: leetcode.com

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

Example

Input: s1 = "internationalization", s2 = "i18n"
Output: true
Explanation: It is possible that "internationalization" was the original string.

Python solution

Python

from functools import lru_cache

def possiblyEquals(s1: str, s2: str) -> bool:
    n1, n2 = len(s1), len(s2)

    def parse_numbers(s: str, i: int):
        nums = []
        val = 0
        for j in range(i, min(len(s), i + 3)):
            if not s[j].isdigit():
                break
            val = val * 10 + int(s[j])
            nums.append((val, j + 1))
        return nums

    @lru_cache(None)
    def dfs(i: int, j: int, diff: int) -> bool:
        if i == n1 and j == n2:
            return diff == 0

        if i < n1 and s1[i].isdigit():
            for val, ni in parse_numbers(s1, i):
                if dfs(ni, j, diff + val):
                    return True

        if j < n2 and s2[j].isdigit():
            for val, nj in parse_numbers(s2, j):
                if dfs(i, nj, diff - val):
                    return True

        if diff > 0:
            if j < n2 and not s2[j].isdigit():
                if dfs(i, j + 1, diff - 1):
                    return True
        elif diff < 0:
            if i < n1 and not s1[i].isdigit():
                if dfs(i + 1, j, diff + 1):
                    return True
        else:
            if i < n1 and j < n2 and not s1[i].isdigit() and not s2[j].isdigit():
                if s1[i] == s2[j] and dfs(i + 1, j + 1, 0):
                    return True
        return False

    return dfs(0, 0, 0)

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings?: LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings is rated Hard on LeetCode.
What topics does LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings cover?: LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings is tagged String and Dynamic Programming on LeetCode.