content: package question0030_substring_with_concatenation_of_all_words;
  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  /**
   * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
   *
   * 单指针+哈希表。
   *
   * 时间复杂度是O(m * n * len)，其中m为字符串s的长度，n为words数组的长度，len为words数组中的单词长度。空间复杂度是O(n)。
   *
   * 执行用时：150ms，击败66.03%。消耗内存：39.3MB，击败96.31%。
   */
  public class Solution1 {
      public List<Integer> findSubstring(String s, String[] words) {
          List<Integer> result = new ArrayList<>();
          int n;
          if (null == words || (n = words.length) == 0) {
              return result;
          }
          int len = words[0].length();
          Map<String, Integer> map = new HashMap<>();
          for (int i = 0; i < n; i++) {
              map.put(words[i], map.getOrDefault(words[i], 0) + 1);
          }
          for (int i = 0; i < s.length() - n * len + 1; i++) {
              Map<String, Integer> tmpMap = new HashMap<>(map);
              int j = 0;
              for (; j < len * n; j += len) {
                  String subString = s.substring(i + j, i + j + len);
                  if (!tmpMap.containsKey(subString)) {
                      break;
                  } else {
                      tmpMap.put(subString, tmpMap.get(subString) - 1);
                      if (tmpMap.get(subString) == 0) {
                          tmpMap.remove(subString);
                      }
                  }
              }
              if (j == len * n) {
                  result.add(i);
              }
          }
          return result;
      }
  }