題目：
1、我的寫法（超時）
從題面自然想到先用回溯算法把words的全排列先算出來，然后遍歷字符串s一次將符合條件的位置加入結果
全排列計算所有可能字符串算法寫法：
這是一個模板用于所有全排列算法的情況，本質思想是回溯。四個參數：words代表候選單詞數組，path代表已經選過的路徑，used代表當前元素有沒有使用過，result代表結果這里用了set去重
在每次回溯開始前先判斷，當前路徑有沒有包含所有候選單詞，如果都包含了的話就加入結果。
從當前path開始算，嘗試所有可能性，把沒用到的元素加入path遞歸，然后恢復數據開始下一次回溯
這是我在外層調用的方法，最后顯示超時了，超時原因在于當words長度過長時，遞歸回溯的方法復雜度不好控制，過于耗時
完整代碼：
class Solution {
? ? public List<Integer> findSubstring(String s, String[] words) {
? ? ? ? //全排列找出words能拼接成的所有字符串
? ? ? ? Set<String> concatStr = new HashSet<>();
? ? ? ? boolean[] used = new boolean[words.length];
? ? ? ? backTrack(words, new ArrayList<>(), used, concatStr);
? ? ? ? //遍歷字符串s，與所有可能的拼接結果對比，找到符合的結果
? ? ? ? int wordLen = 0;
? ? ? ? List<Integer> result = new ArrayList<>();
? ? ? ? for(int i = 0; i < words.length; i++) {
? ? ? ? ? ? wordLen += words[i].length();
? ? ? ? }
? ? ? ? for(int i = 0; i <= s.length() - wordLen; i++) {
? ? ? ? ? ? if(concatStr.contains(s.substring(i, i + wordLen))) {
? ? ? ? ? ? ? ?result.add(i);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return result;
? ? }
? ? private void backTrack(String[] words, List<String> path, boolean[] used, Set<String> result) {
? ? ? ? if(path.size() == words.length) {
? ? ? ? ? ? result.add(String.join("", path));
? ? ? ? }
? ? ? ? for(int i = 0; i < words.length; i++) {
? ? ? ? ? ? if(used[i] == false) {
? ? ? ? ? ? ? ? //如果沒有被用過加入path中
? ? ? ? ? ? ? ? used[i] = true;
? ? ? ? ? ? ? ? path.add(words[i]);
? ? ? ? ? ? ? ? //遞歸回溯
? ? ? ? ? ? ? ? backTrack(words, path, used, result);
? ? ? ? ? ? ? ? //撤銷操作，去掉最后一個元素并標記為未使用
? ? ? ? ? ? ? ? used[i] = false;
? ? ? ? ? ? ? ? path.remove(path.size() - 1);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
2、官方解法
不需要遞歸回溯，用到了異位字符串思想
官解的思路類似于找到字符串中的字母異位詞，只不過它從之前的字母異位變成了字符串異位。注意，體面中words每個單詞的長度都是相等的，所以我們是可以等長的去劃分子串的，這樣劃分之后用哈希表differ去劃分。
遍歷一遍數組，從0開始，直到最后無法滿足長度為止。每次循環，都初始化一個哈希表用來記錄劃分后的單詞出現頻率和words的誤差，等同于之前字符串中找到字母異位詞的做法，只不過這里不再是字母而是一個個長度相等的字符串
完整代碼：
class Solution {
? ? public List<Integer> findSubstring(String s, String[] words) {
? ? ? ? List<Integer> res = new ArrayList<Integer>();
? ? ? ? int m = words.length, n = words[0].length(), ls = s.length();
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? if (i + m * n > ls) {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? Map<String, Integer> differ = new HashMap<String, Integer>();
? ? ? ? ? ? for (int j = 0; j < m; j++) {
? ? ? ? ? ? ? ? String word = s.substring(i + j * n, i + (j + 1) * n);
? ? ? ? ? ? ? ? differ.put(word, differ.getOrDefault(word, 0) + 1);
? ? ? ? ? ? }
? ? ? ? ? ? for (String word : words) {
? ? ? ? ? ? ? ? differ.put(word, differ.getOrDefault(word, 0) - 1);
? ? ? ? ? ? ? ? if (differ.get(word) == 0) {
? ? ? ? ? ? ? ? ? ? differ.remove(word);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? for (int start = i; start < ls - m * n + 1; start += n) {
? ? ? ? ? ? ? ? if (start != i) {
? ? ? ? ? ? ? ? ? ? String word = s.substring(start + (m - 1) * n, start + m * n);
? ? ? ? ? ? ? ? ? ? differ.put(word, differ.getOrDefault(word, 0) + 1);
? ? ? ? ? ? ? ? ? ? if (differ.get(word) == 0) {
? ? ? ? ? ? ? ? ? ? ? ? differ.remove(word);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? word = s.substring(start - n, start);
? ? ? ? ? ? ? ? ? ? differ.put(word, differ.getOrDefault(word, 0) - 1);
? ? ? ? ? ? ? ? ? ? if (differ.get(word) == 0) {
? ? ? ? ? ? ? ? ? ? ? ? differ.remove(word);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (differ.isEmpty()) {
? ? ? ? ? ? ? ? ? ? res.add(start);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}
