#2060

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Check if an Original String Exists Given Two Encoded Strings

Determine if there exists an original string that could produce both encoded inputs using state transition dynamic programming.

string dynamic programming

Problem Statement

Given two strings s1 and s2 composed of lowercase English letters and digits 1-9, determine if there exists an original string that could encode to both. Each encoding replaces consecutive letters with their count or leaves them unchanged. Your task is to return true if such an original string exists, otherwise false.

Each digit in s1 or s2 represents the number of consecutive letters replaced in the encoding. Constraints include 1 <= s1.length, s2.length <= 40, digits limited to 1-9, and consecutive digit sequences do not exceed length 3. Apply dynamic programming to track possible matches between s1 and s2 efficiently.

Examples

Example 1

Input: s1 = "internationalization", s2 = "i18n"

Output: true

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

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

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.

Solution Approach

State Transition Dynamic Programming

Model the problem as DP with states representing positions in s1 and s2 and remaining unmatched letter counts. Transition by consuming letters or numeric placeholders, updating counts and moving indices accordingly.

Handle Numeric Placeholders Carefully

Parse digit sequences in s1 and s2 as numbers and treat them as placeholders for that many letters. Correct handling avoids mismatches and ensures all valid splits of the original string are considered.

Memoization for Efficiency

Use memoization to cache results of state transitions to prevent redundant computation. Each state is uniquely determined by indices in s1 and s2 and current remaining counts, reducing exponential recursion to manageable complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of states, roughly O(n1 * n2 * maxCount^2), where n1 and n2 are lengths of s1 and s2 and maxCount is the maximum consecutive digit value. Space complexity is similar due to memoization storage of each unique DP state.

What Interviewers Usually Probe

Are you considering digits in s1 and s2 as letter counts correctly?
Can you describe the DP state and its transitions for this problem?
Have you memoized overlapping subproblems to avoid recomputation?

Common Pitfalls or Variants

Common pitfalls

Misinterpreting multi-digit numbers in s1 or s2 as separate counts instead of a single placeholder.
Forgetting to track remaining letters when a digit consumes multiple positions in the original string.
Assuming all letters must match directly without accounting for numeric replacements.

Follow-up variants

Check if an original string exists given multiple encoded strings, extending to more than two inputs.
Allow digits in encoding to represent zero letters, introducing optional skips in the original string.
Constrain original strings to only certain alphabets or lengths, adding additional DP restrictions.

FAQ

What is the main approach to solve Check if an Original String Exists Given Two Encoded Strings?

The primary method is state transition dynamic programming, tracking positions and remaining letter counts through memoized recursion.

How do digits in s1 or s2 affect the DP solution?

Digits represent consecutive letters replaced; they modify remaining counts in DP states and require careful parsing of multi-digit sequences.

Can the solution handle strings of length up to 40 efficiently?

Yes, memoization reduces overlapping subproblem computations, making it feasible to handle maximum lengths within constraints.

What common mistakes should I avoid for this problem?

Do not split multi-digit numbers incorrectly, forget remaining letter counts, or assume letters match directly without considering placeholders.

Are there variants of this problem to practice the same pattern?

Yes, variants include multiple encoded strings, optional zero-letter placeholders, or restricted original string alphabets, all using similar DP transitions.

terminal

Solution

Solution 1

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

function possiblyEquals(s1: string, s2: string): boolean {
    const n = s1.length,
        m = s2.length;
    let dp: Array<Array<Set<number>>> = Array.from({ length: n + 1 }, v =>
        Array.from({ length: m + 1 }, w => new Set()),
    );
    dp[0][0].add(0);

    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            for (let delta of dp[i][j]) {
                // s1为数字
                let num = 0;
                if (delta <= 0) {
                    for (let p = i; i < Math.min(i + 3, n); p++) {
                        if (isDigit(s1[p])) {
                            num = num * 10 + Number(s1[p]);
                            dp[p + 1][j].add(delta + num);
                        } else {
                            break;
                        }
                    }
                }

                // s2为数字
                num = 0;
                if (delta >= 0) {
                    for (let q = j; q < Math.min(j + 3, m); q++) {
                        if (isDigit(s2[q])) {
                            num = num * 10 + Number(s2[q]);
                            dp[i][q + 1].add(delta - num);
                        } else {
                            break;
                        }
                    }
                }

                // 数字匹配s1为字母
                if (i < n && delta < 0 && !isDigit(s1[i])) {
                    dp[i + 1][j].add(delta + 1);
                }

                // 数字匹配s2为字母
                if (j < m && delta > 0 && !isDigit(s2[j])) {
                    dp[i][j + 1].add(delta - 1);
                }

                // 两个字母匹配
                if (i < n && j < m && delta == 0 && s1[i] == s2[j]) {
                    dp[i + 1][j + 1].add(0);
                }
            }
        }
    }
    return dp[n][m].has(0);
}

function isDigit(char: string): boolean {
    return /^\d{1}$/g.test(char);
}

Continue Practicing

#2063 vowels of all substrings #2086 minimum number of food buckets to feed the hamsters #2019 the score of students solving math expression