Skip to content

Files

2060

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Sep 13, 2023

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

Example 4:

Input: s1 = "112s", s2 = "g841"
Output: true
Explanation: It is possible that "gaaaaaaaaaaaas" was the original string
- "gaaaaaaaaaaaas"
  -> Split:      ["g", "aaaaaaaaaaaa", "s"]
  -> Replace:    ["1", "12",           "s"]
  -> Concatenate: "112s", which is s1.
- "gaaaaaaaaaaaas"
  -> Split:      ["g", "aaaaaaaa", "aaaa", "s"]
  -> Replace:    ["g", "8",        "4",    "1"]
  -> Concatenate: "g841", which is s2.

Example 5:

Input: s1 = "ab", s2 = "a2"
Output: false
Explanation: It is impossible.
- The original string encoded as s1 has two letters.
- The original string encoded as s2 has three letters.

 

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.

Similar Questions:

Solution 1. DP

// OJ: https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/
// Author: github.com/lzl124631x
// Time: O(C * MN) where `C` is the range of the possible length differences. It's [-10,000, 10,000] in this problem
// Space: O(C * MN)
// Ref: https://leetcode-cn.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/solution/dong-tai-gui-hua-ji-lu-ke-neng-de-chang-o87gp/
class Solution {
public:
    bool possiblyEquals(string s, string t) {
        int M = s.size(), N = t.size();
        unordered_set<int> dp[41][41] = {};
        dp[0][0].insert(0);
        for (int i = 0; i <= M; ++i) {
            for (int j = 0; j <= N; ++j) {
                for (int delta : dp[i][j]) {
                    int num = 0;
                    for (int p = i; p < M && isdigit(s[p]); ++p) {
                        num = num * 10 + (s[p] - '0');
                        dp[p + 1][j].insert(delta + num);
                    }
                    num = 0;
                    for (int p = j; p < N && isdigit(t[p]); ++p) {
                        num = num * 10 + (t[p] - '0');
                        dp[i][p + 1].insert(delta - num);
                    }
                    if (i < M && delta < 0 && isalpha(s[i])) dp[i + 1][j].insert(delta + 1);
                    if (j < N && delta > 0 && isalpha(t[j])) dp[i][j + 1].insert(delta - 1);
                    if (i < M && j < N && delta == 0 && s[i] == t[j]) dp[i + 1][j + 1].insert(0);
                }
            }
        }
        return dp[M][N].count(0);
    }
};

Or

// OJ: https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/
// Author: github.com/lzl124631x
// Time: O(MNC)
// Space: O(MNC) where C is the maximum possible difference of digits. Since there are at most 3 consecutive digits, the difference is at most 1000 (then it must try to match a letter)
// Ref: https://leetcode-cn.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/solution/ji-yi-hua-sou-suo-by-endlesscheng-ll3r/
class Solution {
public:
    bool possiblyEquals(string s, string t) {
        int M = s.size(), N = t.size();
        const int mx = 2001, bias = 1000;
        bool seen[41][41][mx] = {};
        function <bool(int, int, int)> dfs = [&](int i, int j, int d) {
            if (i == M && j == N) return d == 0;
            if (i > M || j > N) return false;
            if (seen[i][j][d + bias]) return false;
            seen[i][j][d + bias] = true;
            if (d == 0 && s[i] == t[j] && dfs(i + 1, j + 1, 0)) return true;
            if (d <= 0) {
                if (isdigit(s[i])) {
                    for (int p = i, num = 0; p < M && isdigit(s[p]); ++p) {
                        num = num * 10 + (s[p] - '0');
                        if (dfs(p + 1, j, d + num)) return true;
                    }
                } else if (d < 0 && dfs(i + 1, j, d + 1)) return true;
            }
            if (d >= 0) {
                if (isdigit(t[j])) {
                    for (int p = j, num = 0; p < N && isdigit(t[p]); ++p) {
                        num = num * 10 + (t[p] - '0');
                        if (dfs(i, p + 1, d - num)) return true;
                    }
                } else if (d > 0 && dfs(i, j + 1, d - 1)) return true;
            }
            return false;  
        };
        return dfs(0, 0, 0);
    }
};