博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode 76. Minimum Window Substring
阅读量:4539 次
发布时间:2019-06-08

本文共 1387 字,大约阅读时间需要 4 分钟。

用unordered_map存储t中的字符和存储的次数,l是字符串最左边的字符的位置,r是字符串最右边字符的位置,count是s中从l到r这一区间成功匹配t中字符个数。当count的个数跟t的大小一样大(也就是成功匹配),就将当前子串的size和min_size比较以更新min_size,会出现一种情况,l位置的字符并不在t中,这样可以继续移动l以求得真正的min_size

class Solution {public:    string minWindow(string s, string t) {        int length1 = s.size();        int length2 = t.size();        if(length1 <= 0 || length2 <= 0)            return "";        unordered_map
container; for(int i = 0;i < length2;i++) container[t[i]]++; int l = 0,count = 0,min_l = 0,min_size = s.size() + 1; for(int r = 0;r < length1;r++){ if(container.find(s[r]) != container.end()){ if(--container[s[r]] >= 0) count++; while(count == t.size()){ int size = r - l + 1; if(size < min_size){ min_l = l; min_size = size; } if(container.find(s[l]) != container.end()){ if(++container[s[l]] > 0) count--; } l++; } } } if(min_size > s.size()) return ""; return s.substr(min_l, min_size); }};

 https://blog.csdn.net/makuiyu/article/details/44570193

转载于:https://www.cnblogs.com/ymjyqsx/p/9788379.html

你可能感兴趣的文章
使用axios向后端传递数据,后端接收不到?
查看>>
List 去处自定义重复对象方法
查看>>
CoreData的使用-1
查看>>
阿里云安装samba
查看>>
jsonp跨域
查看>>
day1-xml语言
查看>>
有谁知道瑞星在windows登录界面图标按钮是如何放上去的吗
查看>>
Delphi高效的字符串处理
查看>>
消息中间件ActiveMQ、RabbitMQ、RocketMQ、ZeroMQ、Kafka如何选型?
查看>>
带宽的理解
查看>>
一、简单工厂模式
查看>>
查询出结果 给其 加上序号的方法 msql
查看>>
阶段1 语言基础+高级_1-3-Java语言高级_05-异常与多线程_第2节 线程实现方式_1_并发与并行...
查看>>
asp.net web.config配置节说明(转发)
查看>>
PPT幻灯片放映时无法全屏的解决方法
查看>>
开发中少不了的Fun -- 微信开发IOS端alert/confirm提示信息,去除网址(URL)的方法...
查看>>
Hibernate学习(二)
查看>>
java IO笔记(DataInput/DataOutput)
查看>>
Day8:String
查看>>
SQL语法之初级增删改查
查看>>