30. Substring with Concatenation of All Words && 76. Minimum Window Substring

30. Substring with Concatenation of All Words

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: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

 Hide Tags

Hide Similar Problems
  (H) Minimum Window Substring
 
 
Brute-force solution: (There are better solutions.)
public class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<>();
    if (s == null || words == null || words.length == 0)
      return res;
    int len = words[0].length(); //all of words are of the same length

    Map<String, Integer> wordCountMap = new HashMap<>();
    for (String w : words)
      wordCountMap.put(w, wordCountMap.containsKey(w) ? wordCountMap.get(w) + 1 : 1);

    for (int i = 0; i <= s.length() - len * words.length; ++i) {
      //the copy of this map keeps the remaining of words to be used.
      Map<String, Integer> copy = new HashMap<>(wordCountMap);

      for (int j = 0; j < words.length; ++j) {
        int start = i + j * len;
        String word = s.substring(start, start + len); // next word
        Integer count = copy.get(word);
        if (count == null)
          break; //the word not in map

        if (count.equals(1))
          copy.remove(word);
        else
          copy.put(word, count - 1);

        //check the map after updates
        if (copy.isEmpty()) {
          res.add(i);
          break;
        }
      }
    }
    return res;
  }
}

 

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

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.

 Hide Tags

 
 
This solution could serve as a template for this type of substring problems.
 
public class Solution {
    public String minWindow(String s, String t) {
    Map<Character, Integer> tcCount = new HashMap<>(t.length());
    for (int i = 0; i < t.length(); ++i) {
      Character c = t.charAt(i);
      Integer count = tcCount.get(c);
      if (count == null)
        tcCount.put(c, 1);
      else
        tcCount.put(c, count + 1);
    }

    int counter = t.length(); // indicate how many more need to be matched.
    int begin = 0, end = 0; //two pointers, one points to head; one tail.
    int d = Integer.MAX_VALUE; //the length of substring

    int head = 0;

    while (end < s.length()) {
      char tailChar = s.charAt(end++);
      Integer tailCharCount = tcCount.get(tailChar);
      if (tailCharCount == null)
        continue;
      if(tailCharCount > 0) // found a matching character.
        --counter;
      tcCount.put(tailChar, tailCharCount - 1); //must allow it to go negative.
      
      while (counter == 0) { //Valid. All character counts in the map == 0.
        if (end - begin < d) {
          head = begin; //cache the updated substring.
          d = end - begin;
        }
        char exitingChar = s.charAt(begin++);
        Integer exitingCharCount = tcCount.get(exitingChar);
        
        if (exitingCharCount == null)
          continue;
        if(exitingCharCount == 0) //the substring no longer matches the condition.
            ++counter;
        tcCount.put(exitingChar, exitingCharCount + 1);
      }
    }
    return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);
  }
}

 

 
 

转载于:https://www.cnblogs.com/neweracoding/p/5679906.html