美文网首页
滑动窗口解决字符串子串问题

滑动窗口解决字符串子串问题

作者: 萌妈码码 | 来源:发表于2018-09-01 14:27 被阅读0次

对很多给定一个字符串,然后要求找到一个满足一定条件的子串的问题,一种比较通用的做法是借助一个MAP,或者是等价的int[128]数组,以及两个指针。由于可以将两个指针看作一个窗口,这种问题也可以叫做滑动窗口问题。下面是解决滑窗问题的一个模板。

public String slideWindow(String s, String t) {
  if(s.length() == 0 || t.length() == 0 || s.length() < t.length()) 
    return "";

  int[] map = new int[128]; //map
  int counter; //check whether the substring is valid
  int begin = 0, end = 0; //two pointers, the window
  int d; //the length of the substring

  for() { /* initialize the hash map here */}

  while(end < s.length()) {
    if(map[s[end++]]-- ?) { /* modify counter here*/}
    while(/* counter condition */) {
      /* update d here if finding minimum */
      //increase begin to make it invalid/valid again
      if(map[s[begin++]]++ ?) { /* modify counter here */ }
    }
    
    /* update d here if finding maximum */
  }
  return d /*? check initial condition*/ ? "" : s.substring(begin,begin + d);
}

76. Minimum Window Substring
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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

public String minWindow(String s, String t) {
        if(s.length() == 0 || t.length() == 0 || s.length() < t.length()) return "";
        
        int[] map = new int[128];
        int counter = t.length();
        int begin = 0, end = 0;
        int d = Integer.MAX_VALUE;
        int head = 0;
        
        for(Character c : t.toCharArray()) map[c] ++;
        
        while(end < s.length()) {
            if(map[s.charAt(end++)]-- > 0) counter --;
            
            while(counter == 0) {
                if(end-begin < d) d = end - (head = begin);
                if(map[s.charAt(begin++)]++ == 0)  counter ++;
            }
        }
        
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head+d);
    }

438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList();
        if(s.length() == 0 || p.length() == 0 || s.length() < p.length()) return res;
        
        int[] map = new int[128];
        int begin = 0, end = 0, counter = p.length(), head = 0;
        
        for(char c : p.toCharArray()) map[c]++;
        while(end < s.length()){
            if(map[s.charAt(end++)]-- > 0) counter --;
            
            while(counter == 0 && begin<end) {
                if((end-(head=begin)) == p.length()) res.add(head);
                if(map[s.charAt(begin++)]++ == 0) counter++;
            }
        }
        return res;    
    }

3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", which the length is 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        
        int[] map = new int[128];
        int begin = 0, end = 0, d = Integer.MIN_VALUE, counter = 0;
        
        while(end < s.length()) {
            if(map[s.charAt(end++)]++ > 0) counter ++;
            
            while(counter > 0) {
                if(map[s.charAt(begin++)]-- > 1) counter --;
            }
        
            if(end - begin > d) {
                d = end - begin;
            }
        }
        return d;
    }

相关文章

  • 滑动窗口解决字符串子串问题

    对很多给定一个字符串,然后要求找到一个满足一定条件的子串的问题,一种比较通用的做法是借助一个MAP,或者是等价的i...

  • 滑动窗口

    核心:如何收缩窗口?具体收缩到哪? 遍历字符串,利用 set 结构存储子串(滑动窗口) 当前字符在滑动窗口中是否存...

  • 滑动窗口算法思想

    滑动窗口算法思想是非常重要的一种思想,可以用来解决数组,字符串的子元素问题。它可以将嵌套循环的问题,转换为单层循环...

  • 子串问题(滑动窗口)

    1.无重复字符的最长子串(3 - 中/剑指48) 题目描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串...

  • 滑动窗口

    滑动窗口用途 用于解决连续子串、连续子数组问题 模式说明 用两个指针,标识窗口边界 用一些状态变量标识窗口当前状态...

  • 面试常见算法与解答

    1、最长不含重复字符的子字符串思路:滑动窗口+检测到重复的进行重新切割

  • LeetCode 最长无重复字符的子串

    题目: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 解题思路使用滑动窗口的思想来解决这个问题...

  • 面试题48_最长不含重复字符的子字符串

    题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 题解一 采用滑动窗口的思...

  • 30.leetcode题目讲解(Python):与所有单词相关联

    题目如下: 通过滑动窗口来取子字符串,并通过字典对象比较单词的出现次数可以求解这个问题。参考代码如下: 其它题目:...

  • 算法和数据结构:整理和推进

    一、滑动窗口类 可能需要上滑动窗口策略的方法: 这个问题的输入是一些线性结构:比如链表呀,数组啊,字符串啊之类的 ...

网友评论

      本文标题:滑动窗口解决字符串子串问题

      本文链接:https://www.haomeiwen.com/subject/uzzywftx.html