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:
L:
S:
"barfoothefoobarman"
L:
["foo", "bar"]
You should return the indices:
(order does not matter).
[0,9]
.(order does not matter).
Solution:O(n)
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L){
if(L==null || L.length==0)
return null;
int n = L.length;
int m = L[0].length();
int l = S.length(); ArrayList<Integer> ret = new ArrayList<Integer>(); Map<String,Integer> cmap = new HashMap<>(); for(int j=0;j<n;j++){ if(cmap.containsKey(L[j])){ cmap.put(L[j],cmap.get(L[j])+1); }else{ cmap.put(L[j], 1); } } int i=0; while(l-i>=n*m){ Map<String, Integer> map = new HashMap<>(cmap); for(int j=0;j<n;j++){ String str = S.substring(i+j*m,i+(j+1)*m); if(map.containsKey(str)){ if(map.get(str)-1==0) map.remove(str); else map.put(str,map.get(str)-1); }else break; } if(map.size()==0) ret.add(i); i++; } return ret; } }
沒有留言:
張貼留言