[数据结构与算法] Leetcode——438. 找到字符串中所有字母异位词

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Leetcode——438. 找到字符串中所有字母异位词 -> 正文阅读

[数据结构与算法]Leetcode——438. 找到字符串中所有字母异位词

概述

438. 找到字符串中所有字母异位词

找到 s 中所有 p 的 异位词 的子串

分析

首先，题目要求我们找出s中的满足条件连续子串，根据之前刷题，连续子串问题可以考虑使用滑动窗口解决

思路

窗口移动的过程中何时记录结果？

因为题目要求寻找的子串要求是p的异位词子串，所以当窗口内的子串是p的异位词时，就可以记录结果
而判断异位词可以选择哈希表来解决

代码

class Solution {
public:
    bool judge(int hash_table[30]) {
        for(int i = 0; i < 30; ++i)
            if (hash_table[i] !=0)  return false;		// 只要窗口内，任意一个字母对应的哈希值不等于0，则该字串就一定不是异位词
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        // 初始化哈希表
        int hash_table[30] = {0,};		
        for (auto c : p)		
            ++hash_table[c - 'a'];

        vector<int> result; 	// 保存结果
        
        // 开始滑动窗口
        int window_begin = 0, window_end = 0;
        for(; window_end < s.size(); ++window_end) {
            --hash_table[s[window_end] - 'a'];		// 只要窗口加入新的元素，就在哈希表中记录
            if (window_end - window_begin == p.size() - 1){			// 如果窗口内的元素个数等于p的元素个数，可以进行判断，是否为p的异位词
                if (judge(hash_table)){
                     result.push_back(window_begin);    	// 满足条件，则记录结果
                }
                ++hash_table[s[window_begin++] - 'a'];		// 窗口左边界向右移；因为子串是固定大小的，所以实际上就是保持固定窗口大小的滑动窗口
            }
        }
        return result;


    }
};