1638. 统计只差一个字符的子串数目 给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。

比方说， “computer” and “computation” 只有一个字符不同： ‘e’/’a’ ，所以这一对子字符串会给答案加 1 。

请你返回满足上述条件的不同子字符串对数目。

一个 子字符串 是一个字符串中连续的字符。

输入：s = “aba”, t = “baba” 输出：6 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对： (“aba”, “baba”) (“aba”, “baba”) (“aba”, “baba”) (“aba”, “baba”) (“aba”, “baba”) (“aba”, “baba”) 加粗部分分别表示 s 和 t 串选出来的子字符串。

输入：s = “ab”, t = “bb” 输出：3 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对： (“ab”, “bb”) (“ab”, “bb”) (“ab”, “bb”) 加粗部分分别表示 s 和 t 串选出来的子字符串。

提示：

• 1 <= s.length, t.length <= 100
• s 和 t 都只包含小写英文字母。

Solutions

class Solution {
    public int countSubstrings(String s, String t) {
     int res = 0;
        for (int i = 1; i < s.length()+1; i++) {
            for (int j = 0, endj=j+i; endj < s.length()+1; j++, endj++) {
                String currentStr = s.substring(j, endj);

                for (int k = 0, endK=k+i; endK < t.length() + 1; k++, endK++) {
                    String kStr = t.substring(k, endK);

                    int diffCount = 0;
                    for (int l = 0; l < currentStr.length(); l++) {
                        if (currentStr.charAt(l)!=kStr.charAt(l)){
                            diffCount++;
                        }

                        if (diffCount>1){
                            break;
                        }
                    }

                    if (diffCount==1){
                        res++;
                    }
                }
            }
        }
        return res;   
    }
}

Ideas

• 方法一：枚举

  题目要求求出字符串 s 与字符串 t 的连续子串中只差一个字符的子串数目，我们枚举 s 与 t 的所有连续子串，然后找其中只含有差一个字符的子串对的数目即可。在实际枚举时，我们可以枚举 s 与 t 的子串的起点 i,j，并依次往后遍历，二者不同的字符个数为 diff，当我们遍历到起点开始的第 k 个字符时:

  • 如果 s[i+k]=t[j+k]，此时 diff 的数目保持不变；
  • 如果 s[i+k] \= t[j+k]，此时 diff 的数目加 1；
  • 如果此时 diff=0 时，我们继续往后遍历；
  • 如果此时 diff=1 时，此时子串 s[i,⋯,(i+k)] 与子串 t[j,⋯,(j+k)] 不同的字符数目为 1，此时计入答案一次；
  • 如果此时 diff>1时，此时 s[i,⋯,(i+k)] 与子串 t[j,⋯,(j+k)] 不同的字符数目大于 1，直接退出遍历；

  我们最终统计出所有的符合题目要求的子串对即可。

  class Solution {
      public int countSubstrings(String s, String t) {
          int m = s.length(), n = t.length();
          int ans = 0;
          for (int i = 0; i < m; i++) {
              for (int j = 0; j < n; j++) {
                  int diff = 0;
                  for (int k = 0; i + k < m && j + k < n; k++) {
                      diff += s.charAt(i + k) == t.charAt(j + k) ? 0 : 1;
                      if (diff > 1) {
                          break;
                      } else if (diff == 1) {
                          ans++;
                      }
                  }
              }
          }
          return ans;
      }
  }