We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if an Original String Exists Given Two Encoded Strings

Difficulty: Hard

Problem Description

Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9, return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

Key Insights

  • The original string can be split into non-empty substrings, some of which can be replaced by their lengths.
  • The encoded strings can start with letters and can have numeric representations of lengths.
  • Consecutive digits in the encoded strings will not exceed 3 characters, simplifying the parsing process.
  • The first character of both encoded strings must match for a common original string to be possible.

Space and Time Complexity

Time Complexity: O(n * m), where n and m are the lengths of s1 and s2, respectively. Space Complexity: O(n * m), for the dynamic programming table.

Solution

We can use a dynamic programming approach to determine if it's possible to derive a common original string from both encoded strings. We'll maintain a 2D boolean array where dp[i][j] indicates whether the first i characters of s1 can match the first j characters of s2.

  1. Initialize dp[0][0] to true, as two empty prefixes can match.
  2. Iterate through each character of s1 and s2, checking if characters match or if we can represent a substring of digits as the length of a substring in the other string.
  3. Fill in the dp table based on matches of characters or valid length representations.
  4. The result will be found in dp[n][m], where n and m are the lengths of s1 and s2.

Code Solutions

def checkOriginalString(s1: str, s2: str) -> bool:
    n, m = len(s1), len(s2)
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(n + 1):
        for j in range(m + 1):
            if i < n and j < m and s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j]

            if i < n and s1[i].isdigit():
                length = 0
                for k in range(i, n):
                    if s1[k].isdigit():
                        length = length * 10 + int(s1[k])
                        if j + length <= m and dp[i + 1][j]:
                            dp[k + 1][j + length] = True
                    else:
                        break

            if j < m and s2[j].isdigit():
                length = 0
                for k in range(j, m):
                    if s2[k].isdigit():
                        length = length * 10 + int(s2[k])
                        if i + length <= n and dp[i][j + 1]:
                            dp[i + length][k + 1] = True
                    else:
                        break

    return dp[n][m]
← Back to All Questions