首页 > 代码库 > 30. Substring with Concatenation of All Words
30. Substring with Concatenation of All Words
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).
2 pointer one stand the first letter, the other go through
public IList<int> FindSubstring(string s, string[] words) { var res = new List<int>(); if(words.Count()==0) return res; var hashtable = new Dictionary<string,int>(); foreach(var word in words) { if(hashtable.ContainsKey(word)) hashtable[word] +=1; else hashtable.Add(word,1); } int wordSize = words[0].Length; for(int j =0;j<= s.Length - words.Count()*wordSize;j++) { var exist = new Dictionary<string,int>(); int i=j; int count =0; while(i<=(s.Length - wordSize)) { string newWord = s.Substring(i,wordSize); if(hashtable.ContainsKey(newWord)) { if(exist.ContainsKey(newWord)) { if(exist[newWord]<hashtable[newWord]) { exist[newWord]++; count++; i += wordSize; if(count ==words.Count()) { res.Add(j); break; } } else break; } else { exist.Add(newWord,1); count++; if(count ==words.Count()) { res.Add(j); break; } i += wordSize; } } else break; } } return res; }
30. Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。