首页 > 代码库 > [leetcode]Substring with Concatenation of All Words
[leetcode]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. 遍历S，每遇到一个字符，就取出wordLength的长度，并验证是否在L中，如不在，i++，如在，进行loop迭代，直到找到一个concatenation （记录下来）或者失配。继续i++，时间复杂度最好为O(n)，最坏为O(n* num * wordLength)
1 public class Solution { 2 List<Integer> list = new ArrayList<Integer>(); 3 public List<Integer> findSubstring(String S, String[] L) { 4 int num = L.length; 5 int wordLength = L[0].length(); 6 if(S.length() < wordLength * num) return list; 7 HashMap<String,Integer> hash = new HashMap<String,Integer>(); 8 for(int i = 0; i < L.length; i++){ 9 if(hash.containsKey(L[i])) hash.put(L[i],hash.get(L[i]) + 1);10 else hash.put(L[i],1);11 }12 HashMap<String,Integer> copy = new HashMap<String,Integer>(hash);13 for(int i = 0; i <= S.length() - wordLength; i++){14 int start = i;15 int end = start + wordLength;16 String sub = S.substring(start, end); 17 if(copy.get(sub)!=null && copy.get(sub) != 0){18 int count = 0;19 boolean canLoop = true;20 while(canLoop){21 copy.put(S.substring(start, end), copy.get(S.substring(start, end)) - 1);22 count++;23 if(count == num){24 list.add(i);25 copy = (HashMap<String,Integer>)hash.clone();26 break;27 }28 start = end;29 end += wordLength;30 if(end > S.length() || !copy.containsKey(S.substring(start, end)) || copy.get(S.subSequence(start, end).toString()) <= 0){31 canLoop = false;32 copy = (HashMap<String,Integer>)hash.clone();33 }34 }35 }36 }37 return list;38 }39 }
思路2：
优化，双指针法，思想类似 Longest Substring Without Repeating Characters， 复杂度可以达到线性。（待验证）
参考链接：
http://blog.csdn.net/ojshilu/article/details/22212703
http://blog.csdn.net/linhuanmars/article/details/20342851
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。