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).
  • 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 ands2 . Otherwise, return false.

Note : The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1
2
3
4
5

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.

Solution

Method 1 – Dynamic Programming with Memoization

Intuition

The key idea is to simulate the decoding process for both strings in parallel, keeping track of how many characters are “skipped” (i.e., replaced by numbers) in each string. We recursively try all possible ways to interpret digits as numbers and match the two strings, using memoization to avoid redundant work.

Approach

  1. Use a recursive function with memoization to avoid recomputation.
  2. At each step, keep track of:
    • The current index in both strings.
    • The number of characters to skip in each string (from previous digit encodings).
  3. If both indices reach the end and both skip counts are zero, return true.
  4. If either string has digits at the current index, try all possible numbers (since up to 3 digits, try 1, 2, or 3 digits).
  5. If both have letters and skip counts are zero, check if the letters match and move forward.
  6. If skip counts are not zero, advance the corresponding index and decrease the skip count.
  7. If none of the above leads to a solution, return false.
  8. Use memoization to cache results for each state.

Code

 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

class Solution {
public:
    bool possiblyEquals(string s1, string s2) {
        unordered_map<string, bool> memo;
        return dfs(s1, s2, 0, 0, 0, memo);
    }
    bool dfs(const string& s1, const string& s2, int i, int j, int diff, unordered_map<string, bool>& memo) {
        string key = to_string(i) + "," + to_string(j) + "," + to_string(diff);
        if (memo.count(key)) return memo[key];
        int n = s1.size(), m = s2.size();
        if (i == n && j == m) return diff == 0;
        if (i < n && isdigit(s1[i])) {
            int val = 0;
            for (int k = i; k < min(i+3, n) && isdigit(s1[k]); ++k) {
                val = val * 10 + (s1[k] - '0');
                if (dfs(s1, s2, k+1, j, diff + val, memo)) return memo[key] = true;
            }
        }
        if (j < m && isdigit(s2[j])) {
            int val = 0;
            for (int k = j; k < min(j+3, m) && isdigit(s2[k]); ++k) {
                val = val * 10 + (s2[k] - '0');
                if (dfs(s1, s2, i, k+1, diff - val, memo)) return memo[key] = true;
            }
        }
        if (diff > 0 && i < n && !isdigit(s1[i])) {
            if (dfs(s1, s2, i+1, j, diff-1, memo)) return memo[key] = true;
        }
        if (diff < 0 && j < m && !isdigit(s2[j])) {
            if (dfs(s1, s2, i, j+1, diff+1, memo)) return memo[key] = true;
        }
        if (diff == 0 && i < n && j < m && !isdigit(s1[i]) && !isdigit(s2[j]) && s1[i] == s2[j]) {
            if (dfs(s1, s2, i+1, j+1, 0, memo)) return memo[key] = true;
        }
        return memo[key] = false;
    }
};
 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

func possiblyEquals(s1 string, s2 string) bool {
    type key struct{ i, j, diff int }
    memo := map[key]bool{}
    var dfs func(i, j, diff int) bool
    dfs = func(i, j, diff int) bool {
        k := key{i, j, diff}
        if v, ok := memo[k]; ok {
            return v
        }
        n, m := len(s1), len(s2)
        if i == n && j == m {
            return diff == 0
        }
        if i < n && s1[i] >= '0' && s1[i] <= '9' {
            val := 0
            for k := i; k < n && k < i+3 && s1[k] >= '0' && s1[k] <= '9'; k++ {
                val = val*10 + int(s1[k]-'0')
                if dfs(k+1, j, diff+val) {
                    memo[k] = true
                    return true
                }
            }
        }
        if j < m && s2[j] >= '0' && s2[j] <= '9' {
            val := 0
            for k := j; k < m && k < j+3 && s2[k] >= '0' && s2[k] <= '9'; k++ {
                val = val*10 + int(s2[k]-'0')
                if dfs(i, k+1, diff-val) {
                    memo[k] = true
                    return true
                }
            }
        }
        if diff > 0 && i < n && (s1[i] < '0' || s1[i] > '9') {
            if dfs(i+1, j, diff-1) {
                memo[k] = true
                return true
            }
        }
        if diff < 0 && j < m && (s2[j] < '0' || s2[j] > '9') {
            if dfs(i, j+1, diff+1) {
                memo[k] = true
                return true
            }
        }
        if diff == 0 && i < n && j < m && (s1[i] < '0' || s1[i] > '9') && (s2[j] < '0' || s2[j] > '9') && s1[i] == s2[j] {
            if dfs(i+1, j+1, 0) {
                memo[k] = true
                return true
            }
        }
        memo[k] = false
        return false
    }
    return dfs(0, 0, 0)
}
 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

class Solution {
    public boolean possiblyEquals(String s1, String s2) {
        Map<String, Boolean> memo = new HashMap<>();
        return dfs(s1, s2, 0, 0, 0, memo);
    }
    private boolean dfs(String s1, String s2, int i, int j, int diff, Map<String, Boolean> memo) {
        String key = i + "," + j + "," + diff;
        if (memo.containsKey(key)) return memo.get(key);
        int n = s1.length(), m = s2.length();
        if (i == n && j == m) return diff == 0;
        if (i < n && Character.isDigit(s1.charAt(i))) {
            int val = 0;
            for (int k = i; k < Math.min(i+3, n) && Character.isDigit(s1.charAt(k)); ++k) {
                val = val * 10 + (s1.charAt(k) - '0');
                if (dfs(s1, s2, k+1, j, diff+val, memo)) return memo.put(key, true) != null || true;
            }
        }
        if (j < m && Character.isDigit(s2.charAt(j))) {
            int val = 0;
            for (int k = j; k < Math.min(j+3, m) && Character.isDigit(s2.charAt(k)); ++k) {
                val = val * 10 + (s2.charAt(k) - '0');
                if (dfs(s1, s2, i, k+1, diff-val, memo)) return memo.put(key, true) != null || true;
            }
        }
        if (diff > 0 && i < n && !Character.isDigit(s1.charAt(i))) {
            if (dfs(s1, s2, i+1, j, diff-1, memo)) return memo.put(key, true) != null || true;
        }
        if (diff < 0 && j < m && !Character.isDigit(s2.charAt(j))) {
            if (dfs(s1, s2, i, j+1, diff+1, memo)) return memo.put(key, true) != null || true;
        }
        if (diff == 0 && i < n && j < m && !Character.isDigit(s1.charAt(i)) && !Character.isDigit(s2.charAt(j)) && s1.charAt(i) == s2.charAt(j)) {
            if (dfs(s1, s2, i+1, j+1, 0, memo)) return memo.put(key, true) != null || true;
        }
        memo.put(key, false);
        return false;
    }
}
 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

class Solution {
    fun possiblyEquals(s1: String, s2: String): Boolean {
        val memo = mutableMapOf<Triple<Int, Int, Int>, Boolean>()
        fun dfs(i: Int, j: Int, diff: Int): Boolean {
            val key = Triple(i, j, diff)
            if (memo.containsKey(key)) return memo[key]!!
            if (i == s1.length && j == s2.length) return diff == 0
            if (i < s1.length && s1[i].isDigit()) {
                var v = 0
                for (k in i until minOf(i+3, s1.length) ) {
                    if (!s1[k].isDigit()) break
                    v = v * 10 + (s1[k] - '0')
                    if (dfs(k+1, j, diff+v)) return true.also { memo[key] = true }
                }
            }
            if (j < s2.length && s2[j].isDigit()) {
                var v = 0
                for (k in j until minOf(j+3, s2.length)) {
                    if (!s2[k].isDigit()) break
                    v = v * 10 + (s2[k] - '0')
                    if (dfs(i, k+1, diff-v)) return true.also { memo[key] = true }
                }
            }
            if (diff > 0 && i < s1.length && !s1[i].isDigit()) {
                if (dfs(i+1, j, diff-1)) return true.also { memo[key] = true }
            }
            if (diff < 0 && j < s2.length && !s2[j].isDigit()) {
                if (dfs(i, j+1, diff+1)) return true.also { memo[key] = true }
            }
            if (diff == 0 && i < s1.length && j < s2.length && !s1[i].isDigit() && !s2[j].isDigit() && s1[i] == s2[j]) {
                if (dfs(i+1, j+1, 0)) return true.also { memo[key] = true }
            }
            memo[key] = false
            return false
        }
        return dfs(0, 0, 0)
    }
}
 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

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        from functools import lru_cache
        n, m = len(s1), len(s2)
        @lru_cache(None)
        def dfs(i: int, j: int, diff: int) -> bool:
            if i == n and j == m:
                return diff == 0
            if i < n and s1[i].isdigit():
                v = 0
                for k in range(i, min(i+3, n)):
                    if not s1[k].isdigit():
                        break
                    v = v * 10 + int(s1[k])
                    if dfs(k+1, j, diff+v):
                        return True
            if j < m and s2[j].isdigit():
                v = 0
                for k in range(j, min(j+3, m)):
                    if not s2[k].isdigit():
                        break
                    v = v * 10 + int(s2[k])
                    if dfs(i, k+1, diff-v):
                        return True
            if diff > 0 and i < n and not s1[i].isdigit():
                if dfs(i+1, j, diff-1):
                    return True
            if diff < 0 and j < m and not s2[j].isdigit():
                if dfs(i, j+1, diff+1):
                    return True
            if diff == 0 and i < n and j < m and not s1[i].isdigit() and not s2[j].isdigit() and s1[i] == s2[j]:
                if dfs(i+1, j+1, 0):
                    return True
            return False
        return dfs(0, 0, 0)
 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

use std::collections::HashMap;
impl Solution {
    pub fn possibly_equals(s1: String, s2: String) -> bool {
        fn dfs(i: usize, j: usize, diff: i32, s1: &Vec<u8>, s2: &Vec<u8>, memo: &mut HashMap<(usize, usize, i32), bool>) -> bool {
            if let Some(&v) = memo.get(&(i, j, diff)) { return v; }
            let n = s1.len();
            let m = s2.len();
            if i == n && j == m { return diff == 0; }
            if i < n && s1[i].is_ascii_digit() {
                let mut v = 0;
                for k in i..(i+3).min(n) {
                    if !s1[k].is_ascii_digit() { break; }
                    v = v * 10 + (s1[k] - b'0') as i32;
                    if dfs(k+1, j, diff+v, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
                }
            }
            if j < m && s2[j].is_ascii_digit() {
                let mut v = 0;
                for k in j..(j+3).min(m) {
                    if !s2[k].is_ascii_digit() { break; }
                    v = v * 10 + (s2[k] - b'0') as i32;
                    if dfs(i, k+1, diff-v, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
                }
            }
            if diff > 0 && i < n && !s1[i].is_ascii_digit() {
                if dfs(i+1, j, diff-1, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
            }
            if diff < 0 && j < m && !s2[j].is_ascii_digit() {
                if dfs(i, j+1, diff+1, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
            }
            if diff == 0 && i < n && j < m && !s1[i].is_ascii_digit() && !s2[j].is_ascii_digit() && s1[i] == s2[j] {
                if dfs(i+1, j+1, 0, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
            }
            memo.insert((i, j, diff), false);
            false
        }
        let s1b = s1.as_bytes().to_vec();
        let s2b = s2.as_bytes().to_vec();
        let mut memo = HashMap::new();
        dfs(0, 0, 0, &s1b, &s2b, &mut memo)
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of the strings (since each index can be up to 40, and skip counts can be up to 120).
  • 🧺 Space complexity: O(n^3) for memoization.