@@ -0,0 +1,2224 @@
+package array;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A/**%0A * https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/%0A * You are given a string, S, and a list of words, L, that are all of the same length.%0A * Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.%0A * %3Cp/%3E%0A * For example, given:%0A * S: %22barfoothefoobarman%22%0A * L: %5B%22foo%22, %22bar%22%5D%0A * You should return the indices: %5B0,9%5D.%0A * (order does not matter).%0A */%0Apublic class SubstringWithConcatenationAllWords %7B%0A    public List%3CInteger%3E findSubstring(String S, String%5B%5D L) %7B%0A        List%3CInteger%3E res = new ArrayList%3C%3E();%0A        if (L == null %7C%7C L.length == 0 %7C%7C S == null %7C%7C S.length() == 0) return res;%0A%0A        int l1 = L%5B0%5D.length();%0A        int l2 = l1 * L.length;%0A        if (l2 %3E S.length()) return res;%0A%0A        Map%3CString, Integer%3E toFound = new HashMap%3C%3E(L.length);%0A        for (int i = 0; i %3C L.length; i++) %7B%0A            Integer count = toFound.get(L%5Bi%5D);%0A            if (count != null) %7B%0A                toFound.put(L%5Bi%5D, count + 1);%0A            %7D else %7B%0A                toFound.put(L%5Bi%5D, 1);%0A            %7D%0A        %7D%0A%0A        Map%3CString, Integer%3E found = new HashMap%3C%3E();%0A        for (int i = 0; i %3C= S.length() - l2; i++) %7B%0A            found.clear();%0A            int j = 0;%0A            for (; j %3C l2; j += l1) %7B%0A                int k = i + j;%0A                String word = S.substring(k, k + l1);%0A                if (!toFound.containsKey(word)) break;%0A                if (!found.containsKey(word)) %7B%0A                    found.put(word, 1);%0A                %7D else %7B%0A                    found.put(word, found.get(word) + 1);%0A                %7D%0A                if (found.get(word) %3E toFound.get(word)) break;%0A            %7D%0A            if (j == l2) res.add(i);%0A        %7D%0A        return res;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        System.out.println(new SubstringWithConcatenationAllWords().findSubstring(%22barfoothefoobarman%22, new String%5B%5D%7B%22foo%22, %22bar%22%7D));%0A        System.out.println(new SubstringWithConcatenationAllWords().findSubstring(%22a%22, new String%5B%5D%7B%22a%22%7D));%0A    %7D%0A%7D%0A

substring with concatenation of all words