Lintcode32 Minimum Window Substring solution 题解

发布时间:2020-07-06 01:23:25 作者:sun511230
来源:网络 阅读:412

【题目描述】

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice:If there is no such window in source that covers all characters in target, return the emtpy string "".If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

给定一个字符串source和一个目标字符串target,在字符串source中找到包括所有目标字符串字母的子串。

注意:如果在source中没有这样的子串,返回"",如果有多个这样的子串,返回起始位置最小的子串。

【题目链接】

http://www.lintcode.com/en/problem/minimum-window-substring/

【题目解析】

可以用窗口型两个指针的思路来解决,外层for循环i = 0 ... n, 内层while循环,条件是j < source.length() 和 !isValid(sourceHash, targetHash),前者是数组下标边界,后者是一个函数,检查当前窗口中的substring是否包含了目标字符串中全部所需的字符,未满足则继续扩大窗口j++,同时更新sourceHash。这里sourceHash,targetHash是整型数组int[],因为ASCII码最多256个,因此用int[]可以作为简化的HashMap使用,key是char对应的int的值,value则是该char在substring中的出现个数。isValid函数则检查sourceHash是否全部包含了targetHash,256个字符一一对应,因此只需一重for循环,如果sourceHash[i] < targetHash[i],则说明有字符未满足条件。

需要注意的是,要设定一个辅助变量记录minStr的长度。

【参考答案】

http://www.jiuzhang.com/solutions/minimum-window-substring/


推荐阅读:
  1. MSSQL Server管理员密码忘记了的解决方法
  2. Python中networkx包有什么用

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

题解 lintcode bs

上一篇:mysql-8.0.16-winx64 安装

下一篇:CentOS环境下安装JDK、Tomcat及相关Linux命令

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》