问题描述:
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 empty string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
原问题链接:https://leetcode.com/problems/minimum-window-substring/
问题分析
这个问题相对比较复杂,主要是对于给定窗口的值和目标值之间的比较匹配和最小窗口的判断。这里结合这两个点来讨论。
首先一个,对于给定的一个源串来说,我怎么知道其中的某一段就包含了目标串里所有的字符呢?尤其是在一个串里还可能有多次重复的元素。一个基本的思路是,我们首先遍历目标串,将它里面每个字符和字符出现的次数都映射保存到一个map里。这样就有了一个保存和比较的基础。对于源串来说,每遍历遇到一个元素的时候就要和目标串建立的map进行比较。可是怎么确保源串的部分正好就涵盖了目标串的所有字符呢?如果每碰到一个就对原来的map里对应的元素减一的话,这样还是不能保证恰好都涵盖了所有的。一种思路是我们用一个变量count来记录目标串的长度。每次在遍历源串的时候,碰到的字符在目标串里存在的,而且在源串里出现的次数小于等于目标串里出现的次数,我们就对count加一。这样直到最后count的值和目标串的长度相等。我们就肯定可以确定,前面这一段是已经涵盖目标串了。
解决了第一个问题之后,下一个问题就是怎么找到最小的窗口呢?这个时候我们就需要从源串的开头去再次遍历这个串。在碰到一个存在于目标串中的元素时,这个位置才可能是窗口的开头。这样就跳过了一些在目标串中不存在的元素。但是这样做还是不够充分的。还有一种情况就是我们遍历过的某一段字符串它里面有些在目标串里也存在的字符出现的次数比目标串里出现的次数还要多。这个时候对于这些存在于源串中但是出现次数更多的情况,我们是可以继续将字符串的位置往后面移的,因为这样肯定保证了串包含了给定的目标串内容,同时也尽量缩小了串的长度。
按照这个思路,我们在具体的实现里用了两个map,一个用来保存目标串t里所有字符和出现的次数。另外一个用来记录遍历源串s时在目标串中出现的字符和次数。我们一边遍历s的时候一边记录符合条件的元素的个数。在发现符合条件的字符串长度达到给定长度时则从头开始进行最小窗口的判断。每次比较后将最小窗口的开始和结束位置保存下来。还有一个情况就是在源串里根本就不可能包含有目标串所有的字符,这里具体的实现就是通过判断位置元素l是否为-1。因为一旦有符合条件的串,l必然参加比较,它也将会被赋值。详细代码实现如下:
public class Solution { public String minWindow(String s, String t) { if(s.isEmpty() || t.isEmpty()) return ""; Map<Character, Integer> itemsFound = new HashMap<>(); Map<Character, Integer> toBeFound = new HashMap<>(); int count = 0, minLen = Integer.MAX_VALUE, l = -1, r = -1; for(int i = 0; i < t.length(); i++) { char c = t.charAt(i); if(toBeFound.containsKey(c)) toBeFound.put(c, toBeFound.get(c) + 1); else toBeFound.put(c, 1); } for(int start = 0, end = 0; end < s.length(); end++) { char e = s.charAt(end); if(!toBeFound.containsKey(e)) continue; if(itemsFound.containsKey(e)) itemsFound.put(e, itemsFound.get(e) + 1); else itemsFound.put(e, 1); if(itemsFound.get(e) <= toBeFound.get(e)) count++; if(count == t.length()) { char ch = s.charAt(start); while(!toBeFound.containsKey(ch) || itemsFound.get(ch) > toBeFound.get(ch)) { if(toBeFound.containsKey(ch) && itemsFound.get(ch) > toBeFound.get(ch)) itemsFound.put(ch, itemsFound.get(ch) - 1); start++; ch = s.charAt(start); } if(end - start < minLen) { minLen = end - start; l = start; r = end; } } } return l == -1 ? "" : s.substring(l, r + 1); } }
这个方法实现的时间复杂度为O(N)。在实际执行的结果里我们会发现它的效率并不是很高。因为这里用的map保存的数据类型和字符串里的char类型等需要进行类型的boxing和unboxing,它在很大程度上拖累了性能。在有的实现里将两个串首先转换成纯字符数组然后再进行统计比较,这样可以极大的提高系统执行的效率。
参考材料
http://articles.leetcode.com/finding-minimum-window-in-s-which/
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode76 LeetCode76_MinimumWindowSubstring
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode 分类 Leetcode Introduction 本文旨在将leetcode的题型分类 Pattern: Sliding window 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 ...
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
Leetcode:Leetcode提交
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
LeetCode 76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 本测试数据是第265个测试用例,字符串长度...
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释