题目描述
解题思路
本题用到了滑动窗口 双指针 哈希
刚开始我是没读懂题的因为我笨
我想把我的思路说一下 左端不轻易缩小 只有找到跟word2匹配了 比如说abbcdd 遍历到c的时候才能匹配这个word2 对吧 那么之后加上以一个d或者俩d 都符合了 然后我们算完了 才能缩小左端 扩大右端
让left先不动 等字符频次和目标频次完全匹配后 right右边剩余的所有字符都可以加到结果字符串中作为符合的子字符串 然后再移动left
代码示例
class Solution {public long validSubstringCount(String word1, String word2) {int n = word1.length();int m = word2.length();// 统计 word2 的字符频次Map<Character, Integer> countWord2 = new HashMap<>();for (char c : word2.toCharArray()) {countWord2.put(c, countWord2.getOrDefault(c, 0) + 1);}// 滑动窗口的字符频次计数器Map<Character, Integer> countWindow = new HashMap<>();int left = 0; // 窗口左边界long result = 0;int matched = 0; // 记录匹配的字符数量// 开始滑动窗口的遍历for (int right = 0; right < n; right++) {// 扩展右端,加入当前字符char rightChar = word1.charAt(right);countWindow.put(rightChar, countWindow.getOrDefault(rightChar, 0) + 1);// 如果该字符在 word2 中存在,且它的频次也匹配了if (countWord2.containsKey(rightChar)) {if (countWindow.get(rightChar).equals(countWord2.get(rightChar))) {matched++;}}// 当窗口中的字符频次与 word2 完全匹配时while (matched == countWord2.size()) {// 计算从当前窗口到字符串末尾的所有合法子串result += (n - right); // 从 right 到字符串末尾的所有子串都是合法的// 缩小左端,移除左边的字符char leftChar = word1.charAt(left);if (countWindow.get(leftChar) > 0) {countWindow.put(leftChar, countWindow.get(leftChar) - 1);}if (countWord2.containsKey(leftChar)) {if (countWindow.get(leftChar) < countWord2.get(leftChar)) {matched--; // 如果频次不再匹配,匹配字符数减少}}left++; // 左端收缩}}return result;}
}