文档章节

最小覆盖子串

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/23 21:27
字数 362
阅读 133
收藏 3

题目

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". Note: If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

思路

我的思路倒是和正确的思路是一样的

双指针思想,尾指针不断往后扫,当扫到有一个窗口包含了所有T的字符,然后再收缩头指针,直到不能再收缩为止。最后记录所有可能的情况中窗口最小的

但是为什么这个想法是对的呢?

另外注意一下自己的那个contains方法,如果是全扫的话容易超时,LeetOJ明显不是按复杂度来算的。

代码

public class Solution {
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    public String minWindow(String S, String T) {
        int i = 0;
        int j = 0;

        int[] count = new int[128];
        int minWindows = Integer.MAX_VALUE;
        String minWindowString="";

        for (char c : T.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }

        for (; j < S.length(); j++) {
            if (contain(count, T)) {
                for (; i <= j; i++) {
                    if (!contain(count, T)) {
                        break;
                    } else {
                        if(minWindows > j-i) {
                            minWindows = j-i;
                            minWindowString = S.substring(i,j);
                        }

                    }
                    // contains i in this iteration
                    count[S.charAt(i)]--;
                }
            }
            // do not contains j in this iteration
            count[S.charAt(j)]++;
        }

        for (; i < j; i++) {
            if (!contain(count, T)) {
                break;
            } else {
                if(minWindows > j-i) {
                    minWindows = j-i;
                    minWindowString = S.substring(i,j);
                }
            }
            count[S.charAt(i)]--;
        }

        // System.out.println(minWindowString);
        if (i == 0) {
            return "";
        }
        return minWindowString;
    }

    private boolean contain(int[] count, String t) {
        for (char character : map.keySet()) {
            if (count[character] < map.get(character)) {
                return false;
            }
        }
        return true;
    }
}

© 著作权归作者所有

共有 人打赏支持
Finley.Hamilton

Finley.Hamilton

粉丝 5
博文 45
码字总数 15431
作品 0
广州
Codeforces 886D - Restoration of string

题目: Codeforces 886F - Restoration of string 翻译 如果一个字符串的子串出现的次数大于任何子串出现的次数,那么这个子串就是 most frequent。给 n 个 most frequent 子串,问最短的原串...

费城的二鹏
2017/11/16
0
0
poj1743 Musical Theme【后缀数组+二分答案】

题目大意: 给n个数组成的串,求是否有多个“相似”且间隔至少为1的子串的长度大于等于5,两个子串相似当且仅当长度相等且每一位的数字差都相等。 解题思路: 首先把问题转化成重复子串的问题...

cdsszjj
01/28
0
0
Google 面试题 | 数组的度数

专栏 | 九章算法 网址 | http://www.jiuzhang.com 1.题目描述 给定元素全为非负整数的非空数组nums,数组的度等于出现最多的元素的次数。找到具有和nums相同度的连续子串的最小长度。 样 例 ...

02/24
0
0
[LeetCode]Degree of an Array 数组的度

链接:https://leetcode.com/problems/degree-of-an-array/description/ 难度:Easy 题目:697. Degree of an Array Given a non-empty array of non-negative integers nums, the degree o......

繁著
2017/12/01
0
0
KMP字符串匹配算法

KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人提出的一种快速模式匹配算法。 KMP朴素算法 原理:子串pattern依次与目标串tar...

长平狐
2013/01/06
167
0

没有更多内容

加载失败,请刷新页面

加载更多

Shell特殊符号总结以及cut,sort,wc,uniq,tee,tr,split命令

特殊符号总结一 * 任意个任意字符 ? 任意一个字符 # 注释字符 \ 脱义字符 | 管道符 # #号后的备注被忽略[root@centos01 ~]# ls a.txt # 备注 a.txt[root@centos01 ~]# a=1[root@centos01...

野雪球
56分钟前
2
0
OSChina 周二乱弹 —— 程序员圣衣

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文:分享Skeeter Davis的单曲《The End of the World》 《The End of the World》- Skeeter Davis 手机党少年们想听歌,请使劲儿戳(这里...

小小编辑
今天
5
0
[ python import module ] 导入模块

import moudle_name ----> import module_name.py ---> import module_name.py文件路径 -----> sys.path (这里进行查找文件) # from app.web import Personimport app.web.Person as Pe......

_______-
昨天
4
0
Redis性能问题排查解决手册

一、性能相关的数据指标 通过Redis-cli命令行界面访问到Redis服务器,然后使用info命令获取所有与Redis服务相关的信息。通过这些信息来分析文章后面提到的一些性能指标。 nfo命令输出的数据可...

IT--小哥
昨天
2
0
mixin混入

①新建mixin.js文件 const mixin = { methods: { /** * 分页公共方法 */ handleSizeChange(val) { this.pageData.size = val; this.query(); }, hand......

不负好时光
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部