Count Substrings That Differ by One Character LeetCode solution in Java

1
// version 1 : O(mn) space
2
class Solution {
3
  public int countSubstrings(String s, String t) {
4
    int m = s.length(), n = t.length();
5

6
    int[][][] dp = new int[m][n][2];
7

8
    int res = 0;
9
    // first col s[0:i] match t[0:0]
10
    for (int i = 0; i < m; i++) {
11
      dp[i][0][0] = (s.charAt(i) == t.charAt(0)) ? 1 : 0;
12
      dp[i][0][1] = (s.charAt(i) == t.charAt(0)) ? 0 : 1;
13
      res += dp[i][0][1];
14
    }
15

16
    // first row s[0:0] match t[0:j]
17
    for (int j = 1; j < n; j++) {
18
      dp[0][j][0] = (s.charAt(0) == t.charAt(j)) ? 1 : 0;
19
      dp[0][j][1] = (s.charAt(0) == t.charAt(j)) ? 0 : 1;
20
      res += dp[0][j][1];
21
    }
22

23
    for (int i = 1; i < m; i++) {
24
      for (int j = 1; j < n; j++) {
25
        dp[i][j][0] = (s.charAt(i) == t.charAt(j)) ? dp[i - 1][j - 1][0] + 1 : 0;
26
        dp[i][j][1] = (s.charAt(i) == t.charAt(j)) ? dp[i - 1][j - 1][1] : dp[i - 1][j - 1][0] + 1;
27
        res += dp[i][j][1];
28
      }
29
    }
30

31
    return res;
32
  }
33
}