[Python] clean top-down DP solution - O(MN)
Idea\n\nWe can use DP to solve this problem. \n\ndp(i, j, k) means the number of substrings ending at s[i] and t[j] and differed by k (0 or 1) character. Please
**Idea**\n\nWe can use DP to solve this problem. \n\n`dp(i, j, k)` means the number of substrings ending at `s[i]` and `t[j]` and differed by `k` (0 or 1) character. Please see code below for bases cases and dp transition function.\n\n</br>\n\n**Complexity**\n\n- Time complexity: `O(MN)`\n- Space complexity: `O(MN)`\n\n</br>\n\n**Python**\n\n```Python\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        \n        m, n = len(s), len(t)\n        \n        @lru_cache(None)\n        def dp(i, j, k):\n            # base cases\n            if i < 0 or j < 0 or k < 0:\n                return 0\n            if k == 0 and s[i] != t[j]:\n                return 0\n            \n            # dp transition\n\t\t\tans = 0\n            if s[i] == t[j]:\n                ans += dp(i-1, j-1, k) + (k == 0)\n            else:\n                ans += dp(i-1, j-1, k-1) + 1\n            \n            return ans\n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                ans += dp(i, j, 1)\n        return ans\n```
[]