11/*
2- Author:King, wangjingui@outlook .com
2+ Author:Andy, nkuwjg@gmail .com
33 Date: Dec 20, 2014
44 Problem: Substring with Concatenation of All Words
55 Difficulty: Easy
@@ -14,10 +14,11 @@ starting indices of substring(s) in S that is a concatenation of each word in L
1414 You should return the indices: [0,9].
1515 (order does not matter).
1616
17- Solution: ...
17+ Solution: 1. Brute + HashMap.
18+ 2. Sliding Window + HashMap. from Sun Mian.
1819*/
1920public class Solution {
20- public List <Integer >findSubstring (String S ,String []L ) {
21+ public List <Integer >findSubstring_1 (String S ,String []L ) {
2122List <Integer >res =new ArrayList <Integer >();
2223if (L .length ==0 ||S ==null ||S .length ()==0 )return res ;
2324int M =S .length (),N =L .length ;
@@ -45,4 +46,41 @@ public List<Integer> findSubstring(String S, String[] L) {
4546 }
4647return res ;
4748 }
49+
50+ public List <Integer >findSubstring_2 (String S ,String []L ) {
51+ List <Integer >list =new ArrayList <>();
52+ Map <String ,Integer >need =new HashMap <>();
53+ for (String str :L ) {
54+ if (need .containsKey (str )) {
55+ need .put (str ,need .get (str )+1 );
56+ }else {
57+ need .put (str ,1 );
58+ }
59+ }
60+ int n =L [0 ].length (),m =L .length ;
61+ for (int i =0 ;i <n ; ++i ) {
62+ Map <String ,Integer >find =new HashMap <>();
63+ for (int start =i ,end =i ,count =0 ;end +n <=S .length ();end +=n ) {
64+ String str =S .substring (end ,end +n );
65+ if (need .get (str ) ==null ) {
66+ start =end +n ;
67+ find .clear ();
68+ count =0 ;
69+ continue ;
70+ }
71+ while (find .get (str ) !=null &&find .get (str ) >=need .get (str )) {
72+ String subStart =S .substring (start ,start +n );
73+ find .put (subStart ,find .get (subStart ) -1 );
74+ start +=n ;
75+ --count ;
76+ }
77+ find .put (str , (find .get (str ) ==null ?0 :find .get (str )) +1 );
78+ ++count ;
79+ if (count !=m )continue ;
80+ list .add (start );
81+ }
82+ }
83+ return list ;
84+ }
85+
4886}
