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)