首页 > 代码库 > Substring with Concatenation of All Words
Substring with Concatenation of All Words
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).
第一遍：
1 public class Solution { 2 int elen = 0; 3 public ArrayList<Integer> findSubstring(String S, String[] L) { 4 // Note: The Solution object is instantiated only once and is reused by each test case. 5 ArrayList<Integer> result = new ArrayList<Integer>(); 6 if(S == null || S.length() == 0) return result; 7 int slen = S.length(); 8 int n = L.length; 9 elen = L[0].length();10 HashMap<String, Integer> hm = new HashMap<String, Integer>();11 for(int i = 0; i < n; i ++){12 if(hm.containsKey(L[i])) hm.put(L[i], hm.get(L[i]) + 1);13 else hm.put(L[i], 1);14 }15 for(int i = 0; i <= slen - n * elen; i ++){16 if(hm.containsKey(S.substring(i, i + elen)))17 if(checkOther(new HashMap<String, Integer>(hm), S, i))18 result.add(i);19 }20 return result;21 }22 public boolean checkOther(HashMap<String, Integer> hm, String s, int pos){23 if(hm.size() == 0) return true;24 if(hm.containsKey(s.substring(pos, pos + elen))){25 if(hm.get(s.substring(pos, pos + elen)) == 1) hm.remove(s.substring(pos, pos + elen));26 else hm.put(s.substring(pos, pos + elen), hm.get(s.substring(pos, pos + elen)) - 1);27 return checkOther(hm, s, pos + elen);28 }29 else return false;30 }31 }
第三遍：
Test case:
1. there can be duplicate in the word lists!!!
1 public class Solution { 2 int llen = 0; 3 int lsize = 0; 4 int slen = 0; 5 List<Integer> result = null; 6 public List<Integer> findSubstring(String S, String[] L) { 7 result = new ArrayList<Integer> (); 8 if(S == null || S.length() == 0 || L == null || L.length == 0 || L[0].length() == 0) return result; 9 lsize = L.length;10 llen = L[0].length();11 slen = S.length();12 HashMap<String, Integer> hs = new HashMap<String, Integer> ();13 for(int i = 0; i < lsize; i ++){14 if(!hs.containsKey(L[i]))15 hs.put(L[i], 1);16 else17 hs.put(L[i], hs.get(L[i]) + 1);18 }19 for(int i = 0; i <= slen - lsize * llen; i ++) 20 findString(S, i, new HashMap<String, Integer> (hs));21 return result;22 }23 24 public void findString(String s, int pos, HashMap<String, Integer> map){25 if(map.size() == 0) result.add(pos - llen * lsize);26 if(pos + llen <= slen && map.containsKey(s.substring(pos, pos + llen))){27 if(map.get(s.substring(pos, pos + llen)) > 1)28 map.put(s.substring(pos, pos + llen), map.get(s.substring(pos, pos + llen)) - 1);29 else30 map.remove(s.substring(pos, pos + llen));31 findString(s, pos + llen, map);32 }33 }34 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。