lc1638. 统计只差一个字符的子串数目

题目链接：LC1638

题解

方法一

• n<100，三层循环枚举。

方法二：动态规划

• 假设 dp[i][j] 代表以 s[i] 和 t[j] 为不同字符的满足题目条件的方案数

代码

class Solution {
public:
    int countSubstrings(string s, string t) {
        int ans = 0;
        for (int i=0;i<s.size();i++) {
            for(int j=0;j<t.size();j++) {
                int d = 0;
                for(int k=0;i+k<s.size()&&j+k<t.size(); k++) {
                    if(s[i+k]!=t[j+k]) {
                        d++;
                    }
                    if(d==2) break;
                    if (d==1) ans +=1;
                }
            }
        }
        return ans;
    }
};