首页 > 其他 > 详细

[头条刷题] 判断一个字符串的组合是否为另一个字符串的子串 leetcode 567

时间:2020-04-25 20:10:37      阅读:132      评论:0      收藏:0      [点我收藏+]


class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.empty()){
            return true;
        }
        if(s2.empty()){
            return false;
        }

        if(s1.size() == 1){
            return s2.find(s1) != std::string::npos;
        }

        if(s1.size() > s2.size()){
            return false;
        }

        std::unordered_map<char, int> umap1;
        std::unordered_map<char, int> umap2;

        for(auto& c: s1){
            umap1[c]++;
        }

        for(int i = 0; i < s1.size(); i++){
            umap2[s2[i]]++;
            if(umap1.find(s2[i]) == umap1.end()){
                umap1[s2[i]] = 0;
            }
        }

        if (umap1 == umap2){
            return true;
        }

        for(int i = s1.size(); i < s2.size(); i++){
            int left = i - s1.size();
            umap2[s2[left]]--;
            umap2[s2[i]]++;
            if(umap1.find(s2[i]) == umap1.end()){
                umap1[s2[i]] = 0;
            }
            // print_map(umap1);
            // print_map(umap2);
            if(umap1 == umap2){
                return true;
            }
        }
        return false;
    }
};

这种方法比较笨, 就是设定一个窗口, 遍历的时候更新窗口, 判断窗口构成的map是否和查询字符串构成的map一致

[头条刷题] 判断一个字符串的组合是否为另一个字符串的子串 leetcode 567

原文:https://www.cnblogs.com/theodoric008/p/12774858.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!