[Python3] top-down & bottom-up dp
\n\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        m, n = len(s), len(t) \n        \n        @cache\n        def fn(i, j, k): \
\n```\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        m, n = len(s), len(t) \n        \n        @cache\n        def fn(i, j, k): \n            """Return number of substrings ending at s[i] and t[j] with k=0/1 difference."""\n            if i < 0 or j < 0: return 0 \n            if s[i] == t[j]: return fn(i-1, j-1, k) + (k==0)\n            else: return 0 if k == 0 else 1 + fn(i-1, j-1, 0)\n        \n        return sum(fn(i, j, 1) for i in range(m) for j in range(n))\n```\n\n```\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        m, n = len(s), len(t)\n        dp0 = [[0]*(n+1) for _ in range(m+1)] # 0-mismatch\n        dp1 = [[0]*(n+1) for _ in range(m+1)] # 1-mismatch\n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                if s[i] == t[j]: \n                    dp0[i+1][j+1] = 1 + dp0[i][j]\n                    dp1[i+1][j+1] = dp1[i][j]\n                else: \n                    dp0[i+1][j+1] = 0\n                    dp1[i+1][j+1] = 1 + dp0[i][j]\n                ans += dp1[i+1][j+1]\n        return ans \n```
['Python3']