Skip to content

2060. Check if an Original String Exists Given Two Encoded Strings

  • Time: $O(|\texttt{s1}||\texttt{s1}| \cdot 2000)$
  • Space: $O(|\texttt{s1}||\texttt{s1}| \cdot 2000)$
 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
61
62
63
64
65
66
67
class Solution {
 public:
  bool possiblyEquals(string s1, string s2) {
    vector<vector<unordered_map<int, bool>>> mem(
        s1.length() + 1, vector<unordered_map<int, bool>>(s2.length() + 1));
    return f(s1, s2, 0, 0, 0, mem);
  }

 private:
  // Returns true if s1[i..n) matches s2[j..n), accounting for the padding
  // difference. Here, `paddingDiff` represents the signed padding. A positive
  // `paddingDiff` indicates that s1 has an additional number of offset bytes
  // compared to s2.
  bool f(const string& s1, const string& s2, int i, int j, int paddingDiff,
         vector<vector<unordered_map<int, bool>>>& mem) {
    if (const auto it = mem[i][j].find(paddingDiff); it != mem[i][j].cend())
      return it->second;
    if (i == s1.length() && j == s2.length())
      return paddingDiff == 0;
    if (i < s1.length() && isdigit(s1[i])) {
      // Add padding on s1.
      const int nextLetterIndex = getNextLetterIndex(s1, i);
      for (const int num : getNums(s1.substr(i, nextLetterIndex - i)))
        if (f(s1, s2, nextLetterIndex, j, paddingDiff + num, mem))
          return true;
    } else if (j < s2.length() && isdigit(s2[j])) {
      // Add padding on s2.
      const int nextLetterIndex = getNextLetterIndex(s2, j);
      for (const int num : getNums(s2.substr(j, nextLetterIndex - j)))
        if (f(s1, s2, i, nextLetterIndex, paddingDiff - num, mem))
          return true;
    } else if (paddingDiff > 0) {
      // `s1` has more padding, so j needs to catch up.
      if (j < s2.length())
        return f(s1, s2, i, j + 1, paddingDiff - 1, mem);
    } else if (paddingDiff < 0) {
      // `s2` has more padding, so i needs to catch up.
      if (i < s1.length())
        return f(s1, s2, i + 1, j, paddingDiff + 1, mem);
    } else {  // paddingDiff == 0
      // There's no padding difference, so consume the next letter.
      if (i < s1.length() && j < s2.length() && s1[i] == s2[j])
        return f(s1, s2, i + 1, j + 1, 0, mem);
    }
    return mem[i][j][paddingDiff] = false;
  }

  int getNextLetterIndex(const string& s, int i) {
    int j = i;
    while (i < s.length() && isdigit(s[j]))
      ++j;
    return j;
  }

  vector<int> getNums(const string& s) {
    vector<int> nums{stoi(s)};
    if (s.length() == 2) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)));
    } else if (s.length() == 3) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 2)));
      nums.push_back(stoi(s.substr(0, 2)) + stoi(s.substr(2, 1)));
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)) +
                     stoi(s.substr(2, 1)));
    }
    return nums;
  }
};

 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
61
62
63
64
65
66
67
68
class Solution {
  public boolean possiblyEquals(String s1, String s2) {
    Map<Integer, Boolean>[][] mem = new Map[s1.length() + 1][s2.length() + 1];
    for (int i = 0; i <= s1.length(); ++i)
      for (int j = 0; j <= s2.length(); ++j)
        mem[i][j] = new HashMap<>();
    return f(s1, s2, 0, 0, 0, mem);
  }

  // Returns true if s1[i..n) matches s2[j..n), accounting for the padding
  // difference. Here, `paddingDiff` represents the signed padding. A positive
  // `paddingDiff` indicates that s1 has an additional number of offset bytes
  // compared to s2.
  private boolean f(final String s1, final String s2, int i, int j, int paddingDiff,
                    Map<Integer, Boolean>[][] mem) {
    if (mem[i][j].containsKey(paddingDiff))
      return mem[i][j].get(paddingDiff);
    if (i == s1.length() && j == s2.length())
      return paddingDiff == 0;
    if (i < s1.length() && Character.isDigit(s1.charAt(i))) {
      // Add padding on s1.
      final int nextLetterIndex = getNextLetterIndex(s1, i);
      for (final int num : getNums(s1.substring(i, nextLetterIndex)))
        if (f(s1, s2, nextLetterIndex, j, paddingDiff + num, mem))
          return true;
    } else if (j < s2.length() && Character.isDigit(s2.charAt(j))) {
      // Add padding on s2.
      final int nextLetterIndex = getNextLetterIndex(s2, j);
      for (final int num : getNums(s2.substring(j, nextLetterIndex)))
        if (f(s1, s2, i, nextLetterIndex, paddingDiff - num, mem))
          return true;
    } else if (paddingDiff > 0) {
      // `s1` has more padding, so j needs to catch up.
      if (j < s2.length())
        return f(s1, s2, i, j + 1, paddingDiff - 1, mem);
    } else if (paddingDiff < 0) {
      // `s2` has more padding, so i needs to catch up.
      if (i < s1.length())
        return f(s1, s2, i + 1, j, paddingDiff + 1, mem);
    } else { // paddingDiff == 0
      // There's no padding difference, so consume the next letter.
      if (i < s1.length() && j < s2.length() && s1.charAt(i) == s2.charAt(j))
        return f(s1, s2, i + 1, j + 1, 0, mem);
    }
    mem[i][j].put(paddingDiff, false);
    return false;
  }

  private int getNextLetterIndex(final String s, int i) {
    int j = i;
    while (j < s.length() && Character.isDigit(s.charAt(j)))
      ++j;
    return j;
  }

  private List<Integer> getNums(final String s) {
    List<Integer> nums = new ArrayList<>(List.of(Integer.parseInt(s)));
    if (s.length() == 2) {
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)));
    } else if (s.length() == 3) {
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 3)));
      nums.add(Integer.parseInt(s.substring(0, 2)) + Integer.parseInt(s.substring(2, 3)));
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)) +
               Integer.parseInt(s.substring(2, 3)));
    }
    return nums;
  }
}

 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
class Solution:
  def possiblyEquals(self, s1: str, s2: str) -> bool:
    def getNums(s: str) -> set[int]:
      nums = {int(s)}
      for i in range(1, len(s)):
        nums |= {x + y for x in getNums(s[:i]) for y in getNums(s[i:])}
      return nums

    def getNextLetterIndex(s: str, i: int) -> int:
      j = i
      while j < len(s) and s[j].isdigit():
        j += 1
      return j

    @functools.lru_cache(None)
    def dp(i: int, j: int, paddingDiff: int) -> bool:
      """
      Returns True if s1[i..n) matches s2[j..n), accounting for the padding
      difference. Here, `paddingDiff` represents the signed padding. A positive
      `paddingDiff` indicates that s1 has an additional number of offset bytes
      compared to s2.
      """
      if i == len(s1) and j == len(s2):
        return paddingDiff == 0
      # Add padding on s1.
      if i < len(s1) and s1[i].isdigit():
        nextLetterIndex = getNextLetterIndex(s1, i)
        for num in getNums(s1[i:nextLetterIndex]):
          if dp(nextLetterIndex, j, paddingDiff + num):
            return True
      # Add padding on s2.
      elif j < len(s2) and s2[j].isdigit():
        nextLetterIndex = getNextLetterIndex(s2, j)
        for num in getNums(s2[j:nextLetterIndex]):
          if dp(i, nextLetterIndex, paddingDiff - num):
            return True
      # `s1` has more padding, so j needs to catch up.
      elif paddingDiff > 0:
        if j < len(s2):
          return dp(i, j + 1, paddingDiff - 1)
      # `s2` has more padding, so i needs to catch up.
      elif paddingDiff < 0:
        if i < len(s1):
          return dp(i + 1, j, paddingDiff + 1)
      # There's no padding difference, so consume the next letter.
      else:  # paddingDiff == 0
        if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
          return dp(i + 1, j + 1, 0)
      return False

    return dp(0, 0, 0)