文档章节

最小覆盖子串

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/23 21:27
字数 362
阅读 126
收藏 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

粉丝 4
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

HTTPS is easy

HTTPS is easy https://www.troyhunt.com/https-is-easy/ HTTPS is easy! In fact, it's so easy I decided to create 4 short videos around 5 minutes each to show people how to enable ......

openthings
18分钟前
0
0
bugList 2

用户端: 1. 上传文件时,当选择:彩色-A3-双面时,第二个图片有bug 应改为 和第一个图片的类型相同 2. 确认打印时,三个下拉选目前有bug 应改为:根据后台配置的商家,group by计算出不同城...

勇恒
21分钟前
2
0
keras cnn 网咯 mnist 分类

搭建貌似比tf是简单很多。。。。。 from keras.datasets import mnistfrom keras.utils import np_utilsfrom keras.models import Sequentialfrom keras.layers import Dense, Activat......

阿豪boy
23分钟前
0
0
解决 /var/run/nginx.pid failed

nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) sudo nginx -c /etc/nginx/nginx.conf nginx -s reload...

驛路梨花醉美
25分钟前
0
0
nginx负载均衡-ssl原理-生成ssl密钥对-nginx配置ssl

nginx负载均衡: 1.创建配置文件 vim /usr/local/nginx/conf/vhost/load.conf #添加以下内容: upstream qq_com #名字自定义,借助此模块定义多个IP,后面...

ZHENG-JY
25分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部