[Python] Brute force
Wasted a lot of time trying to come up with top down DP, but gave up and luckily brute force worked. Just iterate through all substrings of s and t, and check i
Wasted a lot of time trying to come up with top down DP, but gave up and luckily brute force worked. Just iterate through all substrings of s and t, and check if corresponding length substrings differ by 1 letter or less. O(n^3) O(n) time and space. \n\n```\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        def differ(i,j,k):\n            count = 1\n            for l in range(k):\n                if s[i+l] != t[j+l]:\n                    count -= 1\n                if count < 0:\n                    return False\n            return count == 0\n        \n        count = 0\n        for i in range(1,len(s)+1): # length of substring in s\n            for j in range(len(s)-i+1): # iterate through s\n                for k in range(len(t)-i+1): # iterate through t\n                    if differ(j,k,i):\n                        count += 1\n        \n        return count\n```
[]