给定一个字符串 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\ast M)$

空间复杂度

$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\ast M)$

空间复杂度

$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\ast M)$

空间复杂度

$O(N)$