30.串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

C++ class Solution { public: string nstring(string str,int n){ string result_str=""; for( int i=0;i<n;i++ ){ result_str.append(str); } return result_str; } unordered_map<string,int> list2map(vector<string>& temp_vector){ unordered_map<string,int> result_map; for( string temp_str:temp_vector ){ result_map[temp_str]++; } return result_map; } void refillmap(unordered_map<string,int>& result_map,unordered_map<string,int>& data_map){ for( const auto& pair : result_map ){ data_map[pair.first]=pair.second; } } vector<int> findSubstring(string s, vector<string>& words) { vector<int> res; int length = words[0].size();//the length of the word. int total_length=length*words.size();//the total length of the word. if( total_length>s.size() ){ return res; } unordered_map<string,int> result_map=list2map(words); unordered_map<string,int> data_map; refillmap(result_map,data_map); string target_str=""; if(1==data_map.size()){ target_str=nstring(words[0],words.size()); } int gap=length; for( int i=0;i<s.size();i++ ){ if( s.size()-i<total_length){ break; } int n=words.size(); if(1==data_map.size()){ gap=total_length; string current_str=s.substr(i,gap); if(current_str==target_str){ res.push_back(i); } }else{ int a=i; int b=a+(words.size()-1)*length; while( a<=b && n>0 && a<=s.size()-gap && b>=0 ){ string current_str=s.substr(a,gap); string last_str=s.substr(b,gap); if(data_map[current_str]>0){ data_map[current_str]--; n--; a=a+gap; }else{ break; } if(data_map[last_str]>0){ data_map[last_str]--; n--; b=b-gap; }else{ break; } } if(n<words.size() &&(s.size()-i-1)>=total_length){ refillmap(result_map,data_map); } if(0==n){ res.push_back(i); } } } return res; } }; 时间复杂度

O ( N ∗ M ) O(N*M) O(N∗M)

空间复杂度

O ( N ) O(N) O(N)

Java class Solution { Map<String,Integer> list2map(String [] words){ Map<String,Integer> result_map=new HashMap<String,Integer>(); for( String str:words ){ if(result_map.containsKey(str)){ result_map.put(str,result_map.get(str)+1); }else{ result_map.put(str,1); } } return result_map; } String nstring(String str,int n){ StringBuilder strBuilder=new StringBuilder(""); for( int i=0;i<n;i++ ){ strBuilder.append(str); } return strBuilder.toString(); } void refillmap(Map<String,Integer> result_map,Map<String,Integer> data_map){ Set<String> keys = result_map.keySet(); for( String key:keys ){ data_map.put(key,result_map.get(key)); } } public List<Integer> findSubstring(String s, String[] words) { List<Integer> ans=new ArrayList<Integer>(); int length=words[0].length(); int total_length=words.length*length; if( s.length()<total_length ){ return ans; } Map<String,Integer> result_map=list2map(words); Map<String,Integer> data_map=new HashMap<String,Integer>(); refillmap(result_map,data_map); for( int i=0;i<s.length();i++ ){ if( 1==data_map.size() && i+total_length<s.length() ){ String targetString=nstring(words[0],words.length); String tempString=s.substring(i,i+total_length); if(targetString.equals(tempString)){ ans.add(i); } }else{ int a=i; int b=a+(words.length-1)*length; int n=words.length; while(a<=b && a<=s.length()-length && b<=s.length()-length && b>=0 ){ String a_str=s.substring(a,a+length); String b_str=s.substring(b,b+length); if(data_map.containsKey(a_str)&&data_map.get(a_str)>0){ data_map.put(a_str,data_map.get(a_str)-1); n--; a=a+length; }else{ break; } if(data_map.containsKey(b_str)&&data_map.get(b_str)>0){ data_map.put(b_str,data_map.get(b_str)-1); n--; b=b-length; }else{ break; } } if(n<words.length){ refillmap(result_map,data_map); } if(0==n){ ans.add(i); } } } return ans; } } 时间复杂度

O ( N ∗ M ) O(N*M) O(N∗M)

空间复杂度

O ( N ) O(N) O(N)

Python class Solution: def list2map(self,words: List[str]): result_map={}; for str in words: result_map[str]=result_map.get(str,0)+1; return result_map; def refillmap(self,result_map): data_map={}; keys=result_map.keys(); for str in keys: data_map[str]=result_map[str] return data_map; def nstring(self,str,n): result_str=""; for i in range(n): result_str=result_str+str; return result_str; def findSubstring(self, s: str, words: List[str]) -> List[int]: ans=[]; length=len(words[0]); total_length=len(words)*length; result_map=self.list2map(words); data_map=self.refillmap(result_map); for i in range(len(s)): if 1==len(data_map) and (i+total_length<=len(s)): target_str=self.nstring(words[0],len(words)); current_str=s[i:i+total_length]; if target_str==current_str: ans.append(i); else: a=i; b=a+(len(words)-1)*length; n=len(words); while a<=b and a<=len(s)-length and b>=0 and b<=len(s)-length: a_str=s[a:a+length]; b_str=s[b:b+length]; if a_str in data_map and data_map.get(a_str)>0: data_map[a_str]=data_map.get(a_str)-1; n=n-1; a=a+length; else: break; if b_str in data_map and data_map.get(b_str)>0: data_map[b_str]=data_map.get(b_str)-1; n=n-1; b=b-length; else: break; if n<len(words): data_map=self.refillmap(result_map); if 0==n: ans.append(i); return ans; 时间复杂度

O ( N ∗ M ) O(N*M) O(N∗M)

空间复杂度

O ( N ) O(N) O(N)