string类后果之滑动窗口类型

-

  Minimum Window Substring是leetcode上的一道困难,需求在原字符串中找到包罗有目标字符串的最短子字符串,这实质上可了解为最短摘要算法。应用滑动窗口的方法,从左到右增大年夜窗口,先找到包罗有一切目标字符串的窗口,然后再从左到右减小窗口的大年夜小,每次找到窗口时便记录窗口大年夜小。具体做法可参考本文的插图。

  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”.

  一个最短摘要算法的简化版本。

  用到滑动窗口的概念。全部算法的运转过程可经过下图表现,留心仔细体会!

  

  留心

  这个题较难,值得好好了解。

  java代码:

  真心很经典的题目

  1. 应用find all 处理了每次新添加一个节点要用o(256)来辨别可否公道的后果

  2.两个指针,相似于counting sort的思维

  3.用required char[i] 可否大年夜于0来表现可否是我们需求的char

  4.轮回体的控制,外层轮回是不时的把end往后移动,内层轮回是把start向前移动

  5. substring外面 end index 要留心+ 1

  ----------------------------------------------------------------------------------

  You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

  For example, given:

  s:

  words:

  You should return the indices: .

  (order does not matter).

  这道题看似比拟复杂,其实思路和Longest Substring Without Repeating Characters差不多。因为那些单词是定长的,所以实质上和单一个字符一样。和Longest Substring Without Repeating Characters的差别只在于我们需求保护一个字典,然后保证今朝的串包罗字典外面的单词有且唯一一次。思路依然是保护一个窗口,假设以后单词在字典中,则继续移动窗口右端,否则窗口左端可以跳到字符串下一个单词了。假定源字符串的长度为n,字典中单词的长度为l。因为不是一个字符,所以我们需求对源字符串一切长度为l的子串停止辨别。做法是i从0到l-1个字符末尾,掉掉落末尾index辨别为i, i+l, i+2*l, ...的长度为l的单词。如许便可以保证辨别到一切的满足条件的串。因为每次扫描的时间复杂度是O(2*n/l)(每个单词不会被访问多于两次,一次是窗口右端,一次是窗口左端),总共扫描l次(i=0, ..., l-1),所以总复杂度是O(2*n/l*l)=O(n),是一个线性算法。空间复杂度是字典的大年夜小,即O(m*l),个中m是字典的单词数量。

猜你喜欢