smallest window contains query array, preserving order

 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。


import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  public String findShortestSnippet(String doc, String query) {
    HashMap<Character, List<Integer>> invertedIndex = new HashMap<>();
    for (char c : query.toCharArray()) {
      invertedIndex.put(c, new ArrayList<Integer>());
    }
    for (int i = 0; i < doc.length(); i++) {
      char c = doc.charAt(i);
      if (invertedIndex.containsKey(c)) {
        invertedIndex.get(c).add(i);
      }
    }
    int[] points = new int[query.length()];
    String res = "";
    while (points[0] < invertedIndex.get(query.charAt(0)).size()) {
      boolean find = true;
      for (int i = 1; i < points.length; i++) {
        if (points[i] == invertedIndex.get(query.charAt(i)).size()) {
            find = false;
            break;
        }
        while (invertedIndex.get(query.charAt(i)).get(points[i]) <= invertedIndex.get(query.charAt(i - 1)).get(points[i - 1])) {
          points[i]++;
          if (points[i] == invertedIndex.get(query.charAt(i)).size()) {
            find = false;
            break;
          }
        }
        if (!find) {
          break;
        }
      }
      if (find) {
        int end = invertedIndex.get(query.charAt(query.length() - 1)).get(points[points.length - 1]);
        int start = invertedIndex.get(query.charAt(0)).get(points[0]);
        int len = end - start + 1;
        if (res.isEmpty() || len < res.length()) {
          res = doc.substring(start, end + 1);
        }
      }
      points[0]++;
    }
    return res;
  }
 
  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.findShortestSnippet("abcbdbbefgg", "bb"));
  }
}

https://www.quora.com/Given-an-input-array-of-integers-of-size-n-and-a-query-array-of-integers-of-size-k-how-do-I-find-the-smallest-window-of-the-input-array-that-contains-all-the-elements-of-the-query-array-preserving-order?redirected_qid=1374998