1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Substring with Concatenation of All Words
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/
7+ Notes:
8+ You are given a string, S, and a list of words, L, that are all of the same length. Find all
9+ starting indices of substring(s) in S that is a concatenation of each word in L exactly once
10+ and without any intervening characters.
11+ For example, given:
12+ S: "barfoothefoobarman"
13+ L: ["foo", "bar"]
14+ You should return the indices: [0,9].
15+ (order does not matter).
16+
17+ Solution: ...
18+ */
19+ public class Solution {
20+ public List <Integer >findSubstring (String S ,String []L ) {
21+ List <Integer >res =new ArrayList <Integer >();
22+ if (L .length ==0 ||S ==null ||S .length ()==0 )return res ;
23+ int M =S .length (),N =L .length ;
24+ int K =L [0 ].length ();
25+ HashMap <String ,Integer >need =new HashMap <String ,Integer >();
26+ for (String str :L ) {
27+ if (need .containsKey (str )) {
28+ need .put (str ,need .get (str )+1 );
29+ }else {
30+ need .put (str ,1 );
31+ }
32+ }
33+ for (int i =0 ;i <=M -N *K ; ++i ) {
34+ HashMap <String ,Integer >found =new HashMap <String ,Integer >();
35+ int j =0 ;
36+ for (j =0 ;j <N ; ++j ) {
37+ String s =S .substring (i +j *K ,i + (j +1 ) *K );
38+ if (need .containsKey (s ) ==false )break ;
39+ if (found .containsKey (s ) ==true ) {
40+ if (need .get (s ) <=found .get (s ))break ;
41+ found .put (s ,found .get (s )+1 );
42+ }else found .put (s ,1 );
43+ }
44+ if (j ==N )res .add (i );
45+ }
46+ return res ;
47+ }
48+ }
