上海闵行区 网站建设2023年时政热点事件

统计只差一个字符的子串数目【LC1638】

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

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

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

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

• 思路：枚举

  字符串长度最大为100，因此可以枚举s和t每对长度相同的子字符串，记录字符串中不同字符的数目，如果为1，那么答案加1

• 实现

  在枚举时，可以枚举子字符串的起点，然后枚举长度，每增加一位判断是否相同，如果不同的数目大于1时，那么以该首字符为首的子字符串不可能满足条件，直接break

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

  • 复杂度
    • 时间复杂度：$O(m\ast n\ast len)$
    • 空间复杂度：$O(1)$