Python DP O(mn) | O(mn) solution with Thoughts
Intuitive\nAfter brute force , I am thinking this string problems might can use dp(memorized search) to approach due to in O(n^3) solution , we basically will v
**Intuitive**\nAfter brute force , I am thinking this string problems might can use dp(memorized search) to approach due to in O(n^3) solution , we basically will visit same location again and again. \n\n**Transition Equation:**\nFirst , DP array always for the purpose of finding the final res. \nLet\'s use `f(i, j) = the total number of one char differnt subStrs at i-th char of s and j-th char of t`\n\n1. if `s[i] == t[j]`,  then `f(i, j) = f(i-1, j-1)`\n2. if `s[i] != t[j]`, then `f(i, j) = count of same subStr at i-1 th of s and j-1 th of t` + 1 . Note : +1 here is due to we can also not picking anything from previous string , single char at `i` and `j` already forms a solution.\n\nSo , from equation #2 , we need another dp to track at given index `(i, j)`, what will be the count of same substrings as well.\nWe will define `g(i ,j) = the total number of same subStrs at i-th char of s and j-th char of t`\n\nThe whole transition will be \n\n`g(i, j) == 0 if s[i] != s[j] else g(i, j) == g(i-1, j-1) + 1`\n`f(i, j) == f(i-1,j-1) if s[i] == s[j] else g(i-1, j-1)+1` \n\n**Solution**\n\n```\nclass Solution(object):\n    def countSubstrings(self, s, t):\n        """\n        :type s: str\n        :type t: str\n        :rtype: int\n        """\n        m, n = len(s), len(t)\n        sameDP = [[0 for _ in range(n+1)] for _ in range(m+1)] # sameDP[i][j]: The same subStr count at i of s and j of t\n        diffDP = [[0 for _ in range(n+1)] for _ in range(m+1)] # diffDP[i][j]: The 1 char diff subStr count at i of s and j of t  \n        \n        for i in range(m):\n            for j in range(n):\n                sameDP[i+1][j+1] = 0 if s[i]!=t[j] else sameDP[i][j] + 1\n\n        for i in range(m):\n            for j in range(n):\n                diffDP[i+1][j+1] = diffDP[i][j] if s[i] == t[j] else sameDP[i][j] + 1\n        \n        res = 0\n        for i in range(m+1):\n            res += sum(diffDP[i])\n            \n        return res\n```
[]