[Java] clean O(MN)-time O(1)-space Dynamic Programming Solution || with comments
This article aims to: \n1. give a clear definition of entries of 2-Dimension DP-table\n2. give a clear relationship between big problem and sub-problems\n3. opt
This article aims to: \n1. give a clear definition of entries of 2-Dimension DP-table\n2. give a clear relationship between big problem and sub-problems\n3. optimize the "naive" DP-Solution into a O(1)-space Solution\n\nFor some people (myself included), directly coming up with an O(1)-Space Solution is neither easy nor straightforward. So I believe it nice to start with the relatively simple solution first. Then optimize the solution by observing its structure. I believe this is a more of less natural process for the interviewer. \n\nOf course for those who just want the "best" solution, feel free to just go to the very bottom of the article and check the **solution (version 4)**; \n\nFirst of all, let\'s start with the "2-Dimensional" DP-table. Here it seems that it\'s 3-Dimensinoal. However, the third dimension consist just two states. What really matter the most are the index pair (i, j); \n\nFor each (i, j), we count the pairs of substrings (sub_s, sub_t) such that\n1. the last digit of sub_s is s[i]\n2. the last digit of sub_t is t[j]\n        \nThen define the entries in dp-table as:\n* dp\\[i\\]\\[j\\]\\[0\\] : number of such pairs of (sub_s, sub_t) that differs by 0 char\n* dp\\[i\\]\\[j\\]\\[1\\] : number of such pairs of (sub_s, sub_t) that differs by 1 char \n        \nThen relation of bigger problem and sub-problem is very straightforward: \n```\nif (s[i] == t[j])\n\tdp[i][j][0] = dp[i-1][j-1][0] + 1   // plus the substring (s[i], t[j])\n\tdp[i][j][1] = dp[i-1][j-1][1]\nelse \n\tdp[i][j][0] = 0\n\tdp[i][j][1] = dp[i-1][j-1][0] + 1   // plus the substring (s[i], t[j])\n```\n\nThe most basic DP-Solution is as follows: \n\n```\n// version 1 : O(mn) space\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int m = s.length(), n = t.length();\n\n        int[][][] dp = new int[m][n][2];\n        \n        int res = 0;\n        // first col s[0:i] match t[0:0]\n        for (int i = 0; i < m; i++) {\n            dp[i][0][0] = (s.charAt(i) == t.charAt(0)) ? 1 : 0;\n            dp[i][0][1] = (s.charAt(i) == t.charAt(0)) ? 0 : 1;\n            res += dp[i][0][1];\n        }\n      \n        \n        // first row s[0:0] match t[0:j]\n        for (int j = 1; j < n; j++) {\n            dp[0][j][0] = (s.charAt(0) == t.charAt(j)) ? 1 : 0;\n            dp[0][j][1] = (s.charAt(0) == t.charAt(j)) ? 0 : 1;\n            res += dp[0][j][1];\n        }\n        \n        for (int i = 1; i < m; i++) {\n            for (int j = 1; j < n; j++) {\n                dp[i][j][0] = (s.charAt(i) == t.charAt(j)) ? dp[i-1][j-1][0] + 1 : 0;\n                dp[i][j][1] = (s.charAt(i) == t.charAt(j)) ? dp[i-1][j-1][1] : dp[i-1][j-1][0] + 1;\n                res += dp[i][j][1];\n            }\n        }\n\n        return res;\n    }\n}\n```\n\nOr we can rewrite the solution in this compact way: \n\n```\n// version 2 : O(MN) space\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int m = s.length(), n = t.length(), res = 0;\n        int[][][] dp = new int[m+1][n+1][2];\n        \n        // dp[i][j] : count for s[0:i) & t[0:j)\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                dp[i+1][j+1][0] = (s.charAt(i) == t.charAt(j)) ? dp[i][j][0] + 1 : 0;\n                dp[i+1][j+1][1] = (s.charAt(i) == t.charAt(j)) ? dp[i][j][1] : dp[i][j][0] + 1;\n                res += dp[i+1][j+1][1];\n            }\n        }\n        \n        return res;\n    }\n}\n```\n\nNoticing that we only need the left-top entry to calculate current entry. Namely, to calculate dp\\[i+1\\]\\[j+1\\], we only need the values of dp\\[i\\]\\[j\\]. Optimizing the solution into O(min(M,N))-Space is straightforward: \n```\n// version 3: O(min(M, N)) space\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int m = s.length(), n = t.length();\n        if (m < n) return countSubstrings(t, s);\n        \n        int res = 0;\n        int[][] dp = new int[n+1][2];\n        \n        for (int i = 0; i < m; i++) {\n            int[][] next = new int[n+1][2];\n            for (int j = 0; j < n; j++) {\n                next[j+1][0] = (s.charAt(i) == t.charAt(j)) ? dp[j][0] + 1 : 0;\n                next[j+1][1] = (s.charAt(i) == t.charAt(j)) ? dp[j][1] : dp[j][0] + 1;\n                res += next[j+1][1];\n            }\n            \n            dp = next;\n        }\n        \n        return res;\n    }\n}\n```\n\nFurther more, we may reduce the Space Complexity to O(1).  To traverse the whole table, we only need to start traversing from the top and left boundary. Then for each starting point, we just traverse its right-bottom entry until we hit right/bottom boundary. \n\nThis Solution (version 4) is formulated from version 2: \n\n```\n// version 4:  O(1)- space\nclass Solution {\n    private String s;\n    private String t;\n    private int res = 0;\n    public int countSubstrings(String s, String t) {\n        this.s = s;\n        this.t = t;\n        \n        // starting from left boundary dp[0][0], dp[1][0], ..., dp[m-1][0]\n        for (int i = 0; i < s.length(); i++) {\n            traverseRightBottom(i, 0);\n        }\n        \n        // starting from top boundary dp[0][1], dp[0][2], ..., dp[0][n-1]\n        for (int j = 1; j < t.length(); j++) {\n            traverseRightBottom(0, j);\n        }\n        \n        return res;\n    }\n    \n    private void traverseRightBottom(int i, int j) {\n        int prev0 = 0;      // dp[i][j][0]\n        int prev1 = 0;      // dp[i][j][1]\n        \n        while (i < s.length() && j < t.length()) {\n            boolean match = (s.charAt(i++) == t.charAt(j++));\n            int curr0 = match ? prev0 + 1 : 0;            // dp[i+1][j+1][0]\n            int curr1 = match ? prev1     : prev0 + 1;    // dp[i+1][j+1][1]\n            \n            res += curr1; \n            \n            prev0 = curr0;\n            prev1 = curr1;\n        }\n    }\n}\n```
['Dynamic Programming', 'Java']