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

1
var possiblyEquals = function (s1, s2) {
2
  // Memo array, note that we do not need to memoize true results as these bubble up
3
  const dp = Array.from({ length: s1.length + 1 }, () =>
4
    Array.from({ length: s2.length + 1 }, () => [])
5
  );
6

7
  const backtrack = (p1, p2, count) => {
8
    if (p1 === s1.length && p2 === s2.length) return count === 0;
9
    // Optimization: Exit early if we have already visited here and know that it's false
10
    if (dp[p1][p2][count] !== undefined) return dp[p1][p2][count];
11

12
    let c1 = s1[p1];
13
    let c2 = s2[p2];
14

15
    // Case 1: string matches exactly
16
    if (
17
      p1 < s1.length &&
18
      p2 < s2.length &&
19
      c1 === c2 &&
20
      count === 0 &&
21
      backtrack(p1 + 1, p2 + 1, count)
22
    )
23
      return true;
24

25
    // Case 2: we can delete a character
26
    if (
27
      p1 < s1.length &&
28
      isNaN(c1) &&
29
      count < 0 &&
30
      backtrack(p1 + 1, p2, count + 1)
31
    )
32
      return true;
33
    if (
34
      p2 < s2.length &&
35
      isNaN(c2) &&
36
      count > 0 &&
37
      backtrack(p1, p2 + 1, count - 1)
38
    )
39
      return true;
40

41
    // Case 3: we can start stacking numbers to delete
42
    let num = 0;
43
    for (let i = 0; i < 3 && p1 + i < s1.length; i++) {
44
      let c1 = s1[p1 + i];
45
      if (isNaN(c1)) break;
46
      num = num * 10 + parseInt(c1);
47

48
      if (backtrack(p1 + i + 1, p2, count + num)) return true;
49
    }
50

51
    num = 0;
52
    for (let i = 0; i < 3 && p2 + i < s2.length; i++) {
53
      let c2 = s2[p2 + i];
54
      if (isNaN(c2)) break;
55
      num = num * 10 + parseInt(c2);
56

57
      if (backtrack(p1, p2 + i + 1, count - num)) return true;
58
    }
59

60
    dp[p1][p2][count] = false;
61
    return false;
62
  };
63

64
  return backtrack(0, 0, 0);
65
};