You are given a string, S, and a list of words, L, that are all of the same length. 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.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { // Start typing your Java solution below // DO NOT write main() function ArrayList<Integer> result = new ArrayList<Integer>(); if(S== null ||S.length() == 0 || L==null||L.length == 0 ) return result; int lengthofstr = L[0].length(); int lengthofArr = L.length; int totallength = lengthofstr * lengthofArr; HashMap<String,Integer> map = new HashMap<String,Integer>(); for(int i = 0 ; i < lengthofArr; i++){ if(!map.containsKey(L[i])) map.put(L[i],1); } int start = 0; while(start + totallength <= S.length()){ String temp = S.substring(start,start+totallength); String str = temp.substring(0,lengthofstr); if(!map.containsKey(str)){ start++; }else{ ArrayList<String> show = new ArrayList<String>(); for(int j = 0 ; j < L.length; j++){ show.add(temp.substring(j*lengthofstr,(j+1)*lengthofstr)); } for(int j = 0 ; j < L.length; j++){ if(show.contains(L[j])){ show.remove(L[j]); } else{break;} } if(show.isEmpty()){ result.add(start); start += lengthofstr; }else{ start++; } } } return result; } }
public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { // Note: The Solution object is instantiated only once and is reused by each test case. HashMap<String , Integer> need = new HashMap<String , Integer>(); for(int i = 0 ; i < L.length;i++){ need.put(L[i], need.get(L[i]) == null ? 1 : need.get(L[i]) +1); } ArrayList<Integer> result = new ArrayList<Integer>(); for(int i = 0 ; i < L[0].length() ; i++){ populate(result,need,S,L,i); } return result; } public void populate(ArrayList<Integer> result, HashMap<String,Integer> need, String S, String[]L ,int start){ int k = L[0].length(); HashMap<String, Integer> has = new HashMap<String, Integer>(); for(int end = start ; end <= S.length()-k;end+=k){ String sub = S.substring(end,end+k); if(need.containsKey(sub)){ while(has.get(sub)== need.get(sub)){ String tmp = S.substring(start, start + k); has.put(tmp, has.get(tmp) - 1); start += k; } has.put(sub, has.get(sub) == null ? 1 : has.get(sub) + 1); if (end - start + k == L.length * L[0].length()) result.add(start); } else{ has.clear(); start = end + k; } } } }