lintcode-32-最小子串覆盖
2024-09-02 18:06:41
最小子串覆盖
给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。
注意事项
如果在source中没有这样的子串，返回""，如果有多个这样的子串，返回起始位置最小的子串。
说明
在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？
——不需要。样例
给出source = "ADOBECODEBANC"，target = "ABC" 满足要求的解 "BANC"
挑战
要求时间复杂度为O(n)
标签
领英 哈希表 脸书
思路
采用哈希映射记录字符串中每个字母出现的次数，字符ASCII码有128个，所以用大小为128位的数组记录字符串中每个字母出现的次数，如countSource['A']表示A出现的次数，而不是用countSource[0]表示。
先用countTarget数组记录target中每个字符出现的次数，用begin,end记录最小子串覆盖（MVS）在source中的起始位置和结束位置，之后遍历source。
code
class Solution {
public:
/**
* @param source: A string
* @param target: A string
* @return: A string denote the minimum window
* Return "" if there is no such a string
*/
string minWindow(string &source, string &target) {
// write your code here
int sizeSource = source.size(), sizeTarget = target.size();
if(sizeSource == 0) {
return string("");
}
int i, countSource[128], countTarget[128];
for(i=0; i<128; i++) {
countSource[i] = 0;
countTarget[i] = 0;
}
for(i=0; i<sizeTarget; i++) {
countTarget[target[i]]++;
}
int begin = -1, end = sizeSource, start = 0, found = 0, minLen = sizeSource;
for(i=0,start=i; i<sizeSource; i++) {
countSource[source[i]]++;
if (countSource[source[i]] <= countTarget[source[i]]) {
found++;
}
if (found == sizeTarget) {
while (start < i && countSource[source[start]] > countTarget[source[start]]) {
countSource[source[start]]--;
start++;
}
if (i - start < minLen) {
minLen = i - start;
begin = start;
end = i;
}
countSource[source[start++]]--;
found--;
}
}
if (begin == -1) {
return string("");
}
else {
return source.substr(begin, end - begin + 1);
}
}
};
最新文章
- webpack的简单使用
- 【学】React的学习之旅3 - 添加事件(onClick)
- XML转换为对象操作类详解
- sql 中实现打乱数据的排序
- 三层与MVC
- java 使用线程做一个简单的ATM存取款实例.(转)
- 与众不同 windows phone (29) - Communication（通信）之与 OData 服务通信
- 深度理解 Virtual DOM
- 一篇文章读懂Java类加载器
- 转：【Java并发编程】之一：可重入内置锁
- 沉淀，再出发——安装windows10和ubuntu kylin15.04双系统心得体会
- Java笔试题库之选题题篇【1-70题】
- Centos7下安装配置elasticsearch 6.3.1
- 2018-2019-1 20189206 《Linux内核原理与分析》第九周作业
- [转]centos7 移动mysql5.7.19 数据存储位置
- 7、Class文件的格式
- Unable to create new web application
- Activity与Service数据交互：Binder、bindService的用法
- 11-st跳舞消耗体力最少
- 电脑需要重启才能连上WLAN