Check if an Original String Exists Given Two Encoded Strings LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool memo[50][50][2000];
4
  bool comp_seqs(string &s1, string &s2, int i1, int i2, int diff) {
5
    // check true condition
6
    if (i1 == s1.size() && i2 == s2.size()) return diff == 0;
7
    // add 1000 to 'diff' be in range [0, 2000)
8
    bool &ret = memo[i1][i2][diff + 1000];
9
    if (ret) return false; // immediately return
10
    ret = true;            // check visited
11

12
    // diff > 0 or diff < 0 checking to ensure the diff always be in range
13
    // (-1000, 1000) in the case that s1[i1] is a digit
14
    if (diff >= 0 && i1 < s1.size() && s1[i1] <= '9') {
15
      int num1 = 0;
16
      for (int i = 0; i < min(3, (int)s1.size() - i1); i++) { // loop maximum 3 consecutive digits
17
        if (s1[i1 + i] > '9') break;
18
        num1 = num1 * 10 + s1[i1 + i] - '0';
19
        if (comp_seqs(s1, s2, i1 + i + 1, i2, diff - num1)) return true;
20
      }
21
    } else if (diff <= 0 && i2 < s2.size() && s2[i2] <= '9') { // in the case that s2[i2] is a digit
22
      int num2 = 0;
23
      for (int i = 0; i < min(3, (int)s2.size() - i2); i++) {
24
        if (s2[i2 + i] > '9') break;
25
        num2 = num2 * 10 + s2[i2 + i] - '0';
26
        if (comp_seqs(s1, s2, i1, i2 + i + 1, diff + num2)) return true;
27
      }
28
    } else if (diff == 0) {
29
      if (i1 >= s1.size() || i2 >= s2.size() || s1[i1] != s2[i2]) // reject infeasible cases
30
        return false;
31
      return comp_seqs(s1, s2, i1 + 1, i2 + 1, 0);
32
    } else if (diff > 0) {
33
      if (i1 >= s1.size()) // reject infeasible cases
34
        return false;
35
      return comp_seqs(s1, s2, i1 + 1, i2, diff - 1);
36
    } else {
37
      if (i2 >= s2.size()) // reject infeasible cases
38
        return false;
39
      return comp_seqs(s1, s2, i1, i2 + 1, diff + 1);
40
    }
41
    return false;
42
  }
43
  bool possiblyEquals(string s1, string s2) {
44
    return comp_seqs(s1, s2, 0, 0, 0);
45
  }
46
};