Substring with Concatenation of All Words Hard
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).
public List<Integer> findSubstring(String s, String[] words) { if (words.length == 0 || words[0].length() == 0) return new ArrayList<>(); HashMap<String, Integer> map = new HashMap<>(); for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1); List<Integer> list = new ArrayList<>(); int gap = words[0].length(); int nlen = words.length * gap; for (int k = 0; k < gap; k++) { HashMap<String, Integer> wordmap = new HashMap<>(map); for (int startIndex = k, shift = 0; startIndex < s.length() - nlen + 1 && startIndex + shift <= s.length() - gap; ) { String temp = s.substring(startIndex + shift, startIndex + shift + gap); if (wordmap.containsKey(temp)) { wordmap.put(temp, wordmap.get(temp) - 1); if (wordmap.get(temp) == 0) wordmap.remove(temp); if (wordmap.isEmpty()) list.add(startIndex); shift += gap; } else { if (shift == 0) startIndex += gap; else { wordmap.put(s.substring(startIndex, startIndex + gap), wordmap.getOrDefault(s.substring(startIndex, startIndex + gap), 0) + 1); startIndex += gap; shift -= gap; } } } } return list; } 思路：滑动窗口。先把词存入词典，一词一词进行判定（使用起始坐标startIndex和游标shift标记查看过的内容），看有没有在列表中，有就词典中次数-1，如果次数为0就从词典中删除，如果词典为空，则找到一个解。如果下一词不在词典中，则把前面的词收回到词曲，并且游标移动到当前。