文档章节

最小覆盖子串

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/23 21:27
字数 362
阅读 124
收藏 3
点赞 0
评论 0

题目

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
博文 44
码字总数 15431
作品 0
广州
Codeforces 886D - Restoration of string

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

费城的二鹏 ⋅ 2017/11/16 ⋅ 0

poj1743 Musical Theme【后缀数组+二分答案】

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

cdsszjj ⋅ 01/28 ⋅ 0

模式匹配——KMP算法

回头看看KMP算法,感觉还是没有有限自动机那么坑! 朴素的字符串匹配算法想必大家懂得(串下标全部从0计): 模式串P与文本串T匹配,假设扫描到串T的i+1处匹配,串P的j+1处失配,那么下次串T...

WangDylan ⋅ 2013/03/30 ⋅ 2

[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

Google 面试题 | 数组的度数

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

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

最长公共前缀

原题   Write a function to find the longest common prefix string amongst an array of strings. 题目大意   写一个函数找出一个字串所数组中的最长的公共前缀。 解题思路   第一步...

一贱书生 ⋅ 2016/12/12 ⋅ 0

Leetcode402——Remove K Digits

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is ......

Quincuntial ⋅ 2017/04/09 ⋅ 0

Lintcode32 Minimum Window Substring solution 题解

【题目描述】 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 s......

abcdd1234567890 ⋅ 2017/06/04 ⋅ 0

Lintcode32 Minimum Window Substring solution 题解

【题目描述】 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 s......

sun511230 ⋅ 2017/05/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Boost库编译应用

版本:Boost 1.66.0 Windows库编译 官网指南:直接执行bootstrap.bat处理文件即可,可以我却遇到一堆的问题。 环境:Windows 10 + Visual Studio 2017 Boost编译出来库命名 boost库生成文件命...

水海云 ⋅ 6分钟前 ⋅ 0

解决Eclipse发布到Tomcat丢失依赖jar包的问题

如果jar文件是以外部依赖的形式导入的。Eclipse将web项目发布到Tomcat时,是不会自动发布这些依赖的。 可以通过Eclipse在项目上右击 - Propertics - Deployment Assembly,添加“Java Build ...

ArlenXu ⋅ 7分钟前 ⋅ 0

iview tree组件层级过多时可左右滚动

使用vue+iview的tree组件,iview官网iview的tree树形控件 问题描述:tree层级过多时左右不可滚动 问题解决:修改overflow属性值 .el-tree-node>.el-tree-node_children { overflow: vi...

YXMBetter ⋅ 8分钟前 ⋅ 0

分布式锁

通过数据库实现 http://www.weizijun.cn/2016/03/17/%E8%81%8A%E4%B8%80%E8%81%8A%E5%88%86%E5%B8%83%E5%BC%8F%E9%94%81%E7%9A%84%E8%AE%BE%E8%AE%A1/ ZK实现:curator-recipes分布式锁的使用......

素雷 ⋅ 17分钟前 ⋅ 0

Sublime Text3 快捷键

选择类 Ctrl+D 选中光标所占的文本,继续操作则会选中下一个相同的文本。 Alt+F3 选中文本按下快捷键,即可一次性选择全部的相同文本进行同时编辑。举个栗子:快速选中并更改所有相同的变量名...

AndyZhouX ⋅ 23分钟前 ⋅ 0

XamarinAndroid组件教程RecylerView自定义适配器动画

XamarinAndroid组件教程RecylerView自定义适配器动画 如果RecyclerViewAnimators.Adapters命名空间中没有所需要的适配器动画,开发者可以自定义动画。此时,需要让自定义的动画继承Animation...

大学霸 ⋅ 24分钟前 ⋅ 0

eureka 基础(二)

使用Eureka服务器进行身份验证 如果其中一个eureka.client.serviceUrl.defaultZone网址中包含一个凭据(如http://user:password@localhost:8761/eureka)),HTTP基本身份验证将自动添加到您...

明理萝 ⋅ 27分钟前 ⋅ 1

Kubernetes(五) - Service

Kubernetes解决的另外一个痛点就是服务发现,服务发现机制和容器开放访问都是通过Service来实现的,把Deployment和Service关联起来只需要Label标签相同就可以关联起来形成负载均衡,基于kuberne...

喵了_个咪 ⋅ 27分钟前 ⋅ 0

更新队友POM文件后报错

打开报错的地方的pom及其引用方法所在文件的pom,观察其版本号是否一致,不一致进行更改

森火 ⋅ 40分钟前 ⋅ 0

IDEA使用sonarLint

一、IDEA如何安装SonarLint插件 1.打开 Idea 2.点击【File】 3.点击【Settings】 4.点击【Plugins】 5.在搜索栏中输入“sonarlint”关键字 6.点击【Install】进行安装 7.重启Idea 二、IDEA如...

开源中国成都区源花 ⋅ 45分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部