@@ -11,7 +11,7 @@ public static void main(String[] strs) {
1111System .out .println (findSubstring ("lingmindraboofooowingdingbarrwingmonkeypoundcake" ,L ));
1212 }
1313
14- public static List <Integer >findSubstring (String S ,String []L ) {
14+ public static List <Integer >findSubstring1 (String S ,String []L ) {
1515HashMap <String ,Integer >map =new HashMap <String ,Integer >();
1616HashMap <String ,Integer >found =new HashMap <String ,Integer >();
1717List <Integer >ret =new ArrayList <Integer >();
@@ -76,4 +76,58 @@ public static List<Integer> findSubstring(String S, String[] L) {
7676
7777return ret ;
7878 }
79+
80+ // SOLUTION 2:
81+ public static List <Integer >findSubstring (String S ,String []L ) {
82+ HashMap <String ,Integer >map =new HashMap <String ,Integer >();
83+ HashMap <String ,Integer >found ;
84+ List <Integer >ret =new ArrayList <Integer >();
85+
86+ if (S ==null ||L ==null ||L .length ==0 ) {
87+ return ret ;
88+ }
89+
90+ // put all the strings into the map.
91+ for (String s :L ) {
92+ if (map .containsKey (s )) {
93+ map .put (s ,map .get (s ) +1 );
94+ }else {
95+ map .put (s ,1 );
96+ }
97+ }
98+
99+ int lenL =L [0 ].length ();
100+
101+ // 注意这里的条件：i < S.length() - lenL * L.length
102+ // 这里很关键，如果长度不够了，不需要再继续查找
103+ for (int i =0 ;i <=S .length () -lenL *L .length ;i ++) {
104+ // 每一次，都复制之前的hashMap.
105+ found =new HashMap <String ,Integer >(map );
106+
107+ // 一次前进一个L的length.
108+ // 注意j <= S.length() - lenL; 防止越界
109+ for (int j =i ;j <=S .length () -lenL ;j +=lenL ) {
110+ String sub =S .substring (j ,j +lenL );
111+ if (found .containsKey (sub )) {
112+ // 将找到字符串的计数器减1.
113+ found .put (sub ,found .get (sub ) -1 );
114+
115+ // 减到0即可将其移出。否则会产生重复运算，以及我们用MAP为空来判断是否找到所有的单词。
116+ if (found .get (sub ) ==0 ) {
117+ found .remove (sub );
118+ }
119+ }else {
120+ // 不符合条件，可以break,i前进到下一个匹配位置
121+ break ;
122+ }
123+
124+ // L中所有的字符串都已经找到了。
125+ if (found .isEmpty ()) {
126+ ret .add (i );
127+ }
128+ }
129+ }
130+
131+ return ret ;
132+ }
79133}