You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]
You should return the indices: [0,9]. (order does not matter).
Solution
importjava.util.*;/** * Created by ligong on 15/12/2014. */publicclassSolution {publicList<Integer> findSubstring(String S,String[] L) {List<Integer> result =newArrayList<Integer>();if (S ==null||L.length==0)return result;if (S.length() <L[0].length() *L.length)return result;Map<String,Integer> wordLabel =newHashMap<String,Integer>();for (int i =0; i <L.length; i++) {if (!wordLabel.containsKey(L[i])) {wordLabel.put(L[i],0); }wordLabel.put(L[i],wordLabel.get(L[i]) +1); }int m =L.length;int n =L[0].length();int runner =0;while (runner <=S.length() - m * n) {int tempResult =check(S, runner, m, n, wordLabel);if (tempResult >=0) {result.add(tempResult); } runner +=1; }return result; }publicstaticintcheck(String target,int start,int m,int n,Map<String,Integer> wordLabels) {Map<String,Integer> checkMap =newHashMap<String,Integer>();int end = start + (m-1) * n;int runner = start;while (runner <= end) {String current =target.substring(runner, runner + n);if (wordLabels.containsKey(current)) {if (!checkMap.containsKey(current)) {checkMap.put(current,1); } else {checkMap.put(current,checkMap.get(current) +1); }if (wordLabels.get(current) <checkMap.get(current)) {return-1; } } else {return-1; } runner += n; }return start; }}