Problem

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

例子2:

"barfoofoobarthefoobarman"

["bar","foo","the"]

思路

1. 错误思路
   1. 比如barfoo符合要求, 我的方案是start index直接从the开始, 但是需要从bar中的a开始

2. 错误思路2

   1. two pointer

          public List<Integer> findSubstring(String s, String[] words) {
              List<Integer> res = new ArrayList<>();
              if (words == null || s == null) {
                  return res;
              }
              int len = words[0].length();
              int end = 0;
              int begin = 0;
              int startE = 0;
              int startB = 0;
              int count = words.length;
              Map<String, Integer> map = new HashMap<>();
              for (String word: words) {
                  map.put(word, map.getOrDefault(word, 0) + 1);
              }
   
              /*
                  正确的case
                  "barfoothefoobarman"
                  ["foo","bar"]   
   
                  出错的case
                  "aaaaaa"
                  ["aaa","aaa"]
              */
   
              while (end < s.length()) {
                  if (end - begin + 1 < len) {
                      end++;
                      continue;
                  } 
                  String sub = s.substring(begin, end + 1);
                  if (map.containsKey(sub)) {
                      map.put(sub, map.get(sub) - 1);
                      if (map.get(sub) >= 0) count--;
                  }
                  end++;
                  begin++;
   
                  while (count == 0) {
                      if (end - startE == len * words.length) {
                          res.add(startE);
                      }
                      if (startE - startB + 1 < len) {
                          startE++;
                          continue;
                      }
                      String subS = s.substring(startB, startE + 1);
                      if (map.containsKey(subS)) {
                          map.put(subS, map.get(subS) + 1);
                          if (map.get(subS) > 0) count++;
                      }
                      startE++;
                      startB++;
                  }
              }
              return res;
          }
   

3. 正确思路

   1. 首先要问的问题
      1. L数组中的字符串是否会有重复的
      2. s的长度是否一定大于或等于(L的size * word.length)
      3. "aaaaaa", [aa, aa], 答案是0, 1, 2, 3, 4

     public static List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new ArrayList<Integer>();
        if (S == null || L == null || L.length == 0) return res;
        int len = L[0].length(); // length of each word

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

        for (int i = 0; i <= S.length() - len * L.length; i++) {
            Map<String, Integer> copy = new HashMap<String, Integer>(map);
            for (int j = 0; j < L.length; j++) { // checkc if match
                String str = S.substring(i + j*len, i + j*len + len); // next word
                if (copy.containsKey(str)) { // is in remaining words
                    int count = copy.get(str);
                    if (count == 1) copy.remove(str);
                    else copy.put(str, count - 1);
                    if (copy.isEmpty()) { // matches
                        res.add(i);
                        break;
                    }
                } else break; // not in L
            }
        }
        return res;
    }