[Python3] Top down DP O(mn)
Top down DP is always simpler to code. The idea is to calculate the number of good substring pairs for each index pair (i, j), which means s[0, i] and t[0, j]. 
Top down DP is always simpler to code. The idea is to calculate the number of good substring pairs for each index pair `(i, j)`, which means `s[0, i]` and `t[0, j]`. To achieve that, there are two different cases:\n1. `s[i] == s[j]`, then the answer is `diff1(i - 1, j - 1)`, the diff1 function calculates the number of string pairs ending at index `i` and `j` that have exactly one different character.\n2. `s[i] != s[j]`, we found the different character, so the answer will be number of exactly same strings plus pair `(i, j)` itself, namely `1 + same(i - 1, j - 1)` \n\nHere\'s the code.\n```\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        @lru_cache(None)\n        def same(se, te):\n            if se < 0 or te < 0:\n                return 0\n            return 1 + same(se - 1, te - 1) if s[se] == t[te] else 0\n                \n        @lru_cache(None)\n        def diff1(se, te):\n            if se < 0 or te < 0:\n                return 0\n            \n            if s[se] == t[te]:\n                return diff1(se - 1, te - 1)\n            else:\n                return 1 + same(se - 1, te - 1)\n            \n        ans = 0\n        for i in range(len(s)):\n            for j in range(len(t)):\n                ans += diff1(i, j)\n        return ans\n```
[]