文档章节

最小覆盖子串

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/23 21:27
字数 362
阅读 139
收藏 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
[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
Google 面试题 | 数组的度数

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

02/24
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
177
0

没有更多内容

加载失败,请刷新页面

加载更多

Nginx-使用简单总结

下载nginx:http://nginx.org/en/download.html 下载后解压 有很多种方法启动nginx (1)直接双击nginx.exe, 双击后一个黑色的弹窗一闪而过 (2)打开cmd命令窗口,切换到nginx解压目录下, 输入...

Java搬砖工程师
10分钟前
1
0
通过修改控制文件scn推进数据库scn

在数据库遇到ora-600[2662],scn不一致(又没有日志)的时候,我们首先想到的就是去推进数据库的scn,让数据库能够open起来,抢救其中的数据,但是由于各种乱用的情况,oraclescn的pach出来后(11.2...

突突突酱
11分钟前
1
0
Underscore _.template 方法使用详解

https://github.com/hanzichi/underscore-analysis/issues/26 前文 浅谈 Web 中前后端模板引擎的使用 我们简单了解了模板引擎在前后端的应用场景,本文重点深入 Underscore 的模板函数 _.te...

壹峰
12分钟前
0
0
前端缩短数字的长度解决方案[10进制转化为64进制]

function string10to64 (number) { var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_$'.split(''), radix = chars.length, qutient =......

未来cc
12分钟前
0
0
十年架构师不到400行手写一个Spring MVC

首先,我们先来介绍一下Spring的三个阶段,配置阶段、初始化阶段和运行阶段(如图): 配置阶段:主要是完成application.xml配置和Annotation配置。 初始化阶段:主要是加载并解析配置信息,...

小刀爱编程
13分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部