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

1
/**
2
 * Cases:
3
 *
4
 * <p>diff > 0 meaning we need to pick more chars in s1 diff < 0 meaning we need to pick more chars
5
 * in s2
6
 *
7
 * <p>-1000 < diff < 1000 as there can be at most 3 digits in the string meaning largest digits are
8
 * 999
9
 *
10
 * <p>1. s1[i] == s2[j] and diff = 0 increment i+1 and j+1
11
 *
12
 * <p>2. if s1[i] is not digit and diff > 0 then increment i i+1, diff 3. if s2[j] is not digit and
13
 * diff < 0 then increment j j+1, diff 4. if s1[i] is digit then get digit value and decrement diff
14
 * val as we have covered such chars in the s1 string and increment i i+1, diff-val 5. if s2[j] is
15
 * digit then get digit value and increment diff val as we need to cover such chars in the s2 string
16
 * and increment j, j+1, diff+val
17
 *
18
 * <p>01234 s1 = l123e s2 = 44
19
 *
20
 * <p>i: 0 j: 0 diff: 0 // Wildcard matching on s2[j] val = 4, diff = 0+4 j = 1
21
 *
22
 * <p>i: 0 j: 1 diff: 4 // Literal matching on s1[i] increment ith pointer as ith is a literal and
23
 * we can move on to next char in s1 and decrement diff
24
 *
25
 * <p>i: 1 j: 1 diff: 3 // Wildcard matching on s1[i] val = 1 diff = 3-1 = 2 increment i
26
 *
27
 * <p>i: 2 j: 1 diff: 2 // Wildcard matching on s1[i] val = 2 diff = 2-2 = 0 increment i
28
 *
29
 * <p>i: 3 j: 1 diff: 0 // Wildcard matching on s1[i] val=3 diff = 0-3 = -3, increment i
30
 *
31
 * <p>i: 4 j: 1 diff: -3 // Wildcard matching on s2[j] val = 4 diff = -3+4 =1 increment j
32
 *
33
 * <p>i: 4 j: 2 diff: 1 // Literal matching on s1[i] decrement i-1 and increment i
34
 *
35
 * <p>i=5 j=2 diff==0 return true dp[4][2][1] = true return true return dp[4][1][1000-3] = true
36
 * return dp[3][1][0] = true
37
 *
38
 * <p>i: 2 j: 1 diff: 2 return dp[2][1][2] = true return true
39
 *
40
 * <p>i: 0 j: 1 diff: 4 return dp[0][1][4] = true return true
41
 */
42
class Solution {
43
  // 112ms
44
  public boolean possiblyEquals(String s1, String s2) {
45
    return helper(
46
        s1.toCharArray(),
47
        s2.toCharArray(),
48
        0,
49
        0,
50
        0,
51
        new Boolean[s1.length() + 1][s2.length() + 1][2001]);
52
  }
53

54
  boolean helper(char[] s1, char[] s2, int i, int j, int diff, Boolean[][][] dp) {
55
    if (i == s1.length && j == s2.length) {
56
      return diff == 0;
57
    }
58

59
    if (dp[i][j][diff + 1000] != null) return dp[i][j][diff + 1000];
60

61
    // if both i and j are at the same location and chars are same then simply increment both
62
    // pointers
63
    if (i < s1.length && j < s2.length && diff == 0 && s1[i] == s2[j]) {
64
      if (helper(s1, s2, i + 1, j + 1, diff, dp)) {
65
        return dp[i][j][diff + 1000] = true;
66
      }
67
    }
68

69
    // if s1[i] is literal and diff > 0 then increment i and decrement diff by 1
70
    if (i < s1.length
71
        && !Character.isDigit(s1[i])
72
        && diff > 0
73
        && helper(s1, s2, i + 1, j, diff - 1, dp)) {
74
      return dp[i][j][diff + 1000] = true;
75
    }
76

77
    // if s2[j] is literal and diff < 0 then increment j and increment diff by 1
78
    // as we are done with the current jth char
79
    if (j < s2.length
80
        && !Character.isDigit(s2[j])
81
        && diff < 0
82
        && helper(s1, s2, i, j + 1, diff + 1, dp)) {
83
      return dp[i][j][diff + 1000] = true;
84
    }
85

86
    // wildcard matching in s1
87
    // if s1 contains l123
88
    // then need to check with val as 1 then val as 12 and val as 123
89
    for (int k = i, val = 0; k < i + 4 && k < s1.length && Character.isDigit(s1[k]); k++) {
90
      val = val * 10 + s1[k] - '0';
91
      if (helper(s1, s2, k + 1, j, diff - val, dp)) {
92
        return dp[i][j][diff + 1000] = true;
93
      }
94
    }
95

96
    // wildcard matching in s2
97
    // if s2 contains l123
98
    // then need to check with val as 1 then val as 12 and val as 123
99
    for (int k = j, val = 0; k < j + 4 && k < s2.length && Character.isDigit(s2[k]); k++) {
100
      val = val * 10 + s2[k] - '0';
101
      if (helper(s1, s2, i, k + 1, diff + val, dp)) {
102
        return dp[i][j][diff + 1000] = true;
103
      }
104
    }
105

106
    return dp[i][j][diff + 1000] = false;
107
  }
108
}