给出一个字符串S和一组单词L,L中单词的长度都相等,找出S中的符合以下要求的子串在S中的起始位置索引:子串为L中所有单词串联在一起(单词的顺序随意),L中的每个单词只出现一次,中间不能有其他的字符。
例如:给定S="nowcoderacodnowert",L为["now", "cod"],
返回的索引应该是[0,9].(不用关心给出索引的顺序)
vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string, int> counts;//存储每个单词的次数 for (string word : words) counts[word]++; int n = s.length(), num = words.size(), len = words[0].length(); vector<int> indexes; for (int i = 0; i < n - num * len + 1; i++) { //i代表起点 unordered_map<string, int> seen;//存储i为起点的字符串里指定单词的次数 int j = 0;//表示单词数目,只有当j==num时,才找到了所有单词 for (; j < num; j++) { string word = s.substr(i + j * len, len);//以i为起点,长度为len的第j个单词 if (counts.find(word) != counts.end()) { seen[word]++; if (seen[word] > counts[word])//如果此单词出现次数超出,则i位置不合法 break; } else break;//如果此单词不存在于counts里,i位置不合法 } if (j == num) indexes.push_back(i);//i==num,则i是合法位置之一 } return indexes; }
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> indexs = new ArrayList<Integer>(); Map<String, Integer> map_L = new HashMap<String, Integer>(); Map<String, Integer> map_temp = new HashMap<String, Integer>(); int wordsnum = L.length, wordlen = L[0].length(); for (String str : L) { if(map_L.containsKey(str)){ map_L.put(str, map_L.get(str)+1); }else{ map_L.put(str, 1); } } for(int i = 0 ; i < S.length()-wordsnum*wordlen+1; i++){ int count = 0; map_temp.clear(); for(int j = i;j<wordsnum*wordlen+i;j+=wordlen){ String tmp = S.substring(j, j+wordlen); if(map_L.containsKey(tmp)){ if(map_temp.containsKey(tmp)){ map_temp.put(tmp, map_temp.get(tmp)+1); }else{ map_temp.put(tmp, 1); } count++; }else{ break; } if(map_temp.get(tmp)>map_L.get(tmp)){ break; } if(count == wordsnum){ indexs.add(i); } } } return indexs; } }
//说好的order does not matter,最后怎么还是需要按照从小到达的顺序呢? public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (S==null||S.length()==0||L==null||L.length==0){
return res;
}
HashMap<String,Integer> dict = new HashMap<String,Integer>();
int word_len=L[0].length();
for(String word:L){
if(dict.containsKey(word)){
dict.put(word, dict.get(word)+1);
}else{
dict.put(word, 1);
}
}
for(int i=0;i<word_len;i++){
int count =0;//计算出现的单词的个数
int index =i;
HashMap<String,Integer> win = new HashMap<String,Integer>();
for(int j=i;j<=S.length()-word_len;j+=word_len){
String tmp = S.substring(j,j+word_len);
if(dict.containsKey(tmp)){//如果值出现在集合里
if(win.containsKey(tmp)){//如果值出现在窗口里
win.put(tmp, win.get(tmp)+1);
}else{
win.put(tmp,1);
}
if(win.get(tmp)<=dict.get(tmp)){
count++;
}else{
while(win.get(tmp)>dict.get(tmp)){
String s=S.substring(index,index+word_len);
win.put(s, win.get(s)-1);
if(win.get(s)<dict.get(s)){
count--;
}
index=index+word_len;
}
}
if(count==L.length){
res.add(index);
String s1= S.substring(index,index+word_len);
win.put(s1, win.get(s1)-1);
index = index+word_len;
count--;
}//j结束
}else{//如果不出现在集合里,那么将要从窗口最右面重新开始
win.clear();
count=0;
index=j+word_len;
}
}
}//i结束
Collections.sort(res);//为什么必须排序后才通过呢?
return res;
}
}
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { map<string,int> M; vector<int> v; for(string s: L) M[s]++; int n = S.size(); int m = L.size(); int l = L[0].size(); for(int i=0;i<n-m*l+1;i++) { map<string,int> T; int k = 0; for(;k<m;k++) { string s = S.substr(i+k*l,l); if(M.find(s) != M.end()) { T[s]++; if(T[s] > M[s]) break; }else break; } if(k == m) v.push_back(i); } return v; } };
//字符串的模式匹配变型 /*1)L中存在重复的元素2)子串不允许间断,即子串从开始到找全L中的所有元素之前,子串中不允许包含L以外的东西,而且,即使当前处理的子串是L中含有的,但是前面已经找够了,这个多余的也是不合法的,若此时还有L中的其他元素没找到,从这个起点开始也是不成功的。
3)L在S中出现的顺序不同考虑,任意顺序,只要全部存在就可以。
分析:
1)先对L中的所有元素做个统计,定义一个hash map<string, int> 型 变量total,统计每个词出现的次数,另外定义一个同类型的count,用来记录到目前为止,已经找到的L中的元素情况,当全部找全的时候就找到了一个合法的起始点。然后将count清空,继续找。
2)整体的框架与传统的字符串匹配一致,不同的是这里不要求顺序,所以似乎在S中不能加速移动。*/
import java.util.*; public class Solution { public ArrayList<Integer> findSubstring(String s, String[] strs) { ArrayList<Integer> array=new ArrayList(); if(s == null||s.length() == 0||strs == null||strs.length == 0||s.length() < strs[0].length()){ return array; } HashMap<String,Integer> map=new HashMap(); for(int i=0;i<strs.length;i++){//统计每个串出现的次数 if(!map.containsKey(strs[i])){ map.put(strs[i],1); }else{ map.put(strs[i],map.get(strs[i])+1); } } HashMap<String,Integer> count;//暂时统计出现次数 int inlen=strs[0].length(); int dstlen=inlen*strs.length; for(int i=0;i <= s.length()-dstlen;i++){ int j=i; count=new HashMap(); int cur=0; for(;cur<strs.length;cur++){ String curstr=s.substring(j,j+inlen); if(!map.containsKey(curstr)){ break; } if(!count.containsKey(curstr)){ count.put(curstr,1); }else if(count.get(curstr) < map.get(curstr)){ count.put(curstr,count.get(curstr)+1); }else{ break; } j=j+inlen; } if(cur == strs.length){ array.add(i); } } return array; } }
class Solution { public: vectorfindSubstring(string s, vector& words) { unordered_map<string> counts;//存储每个单词的次数 for (string word : words) counts[word]++; int n = s.length(), num = words.size(), len = words[0].length(); vectorindexes; for (int i = 0; i < n - num * len + 1; i++) { //i代表起点 unordered_map<string> seen;//存储i为起点的字符串里指定单词的次数 int j = 0;//表示单词数目,只有当j==num时,才找到了所有单词 for (; j < num; j++) { string word = s.substr(i + j * len, len);//以i为起点,长度为len的第j个单词 if (counts.find(word) != counts.end()) { seen[word]++; if (seen[word] > counts[word])//如果此单词出现次数超出,则i位置不合法 break; } else break;//如果此单词不存在于counts里,i位置不合法 } if (j == num) indexes.push_back(i);//i==num,则i是合法位置之一 } return indexes; } };</string></string>
unordered_map<string, int> dict, c_dict; int len = L[0].size(); vector<int> res; if (S.empty() || L.empty() || S.size() < len * L.size()) return res; for (int i = 0; i < L.size(); ++i) { if (dict.find(L[i]) != dict.end()) dict[L[i]]++; else dict[L[i]] = 1; } c_dict = dict; int count = 0, num = L.size(); for (int i = 0; i <= S.size() - len * num; ++i) { string word = S.substr(i, len * num); dict = c_dict; count = 0; for (int j = 0; j <= word.size() - len; j += len) { string str = word.substr(j, len); if (dict.find(str) != dict.end()) { if (dict[str] > 0) { dict[str]--; count++; } else break; } else break; } if (count == num) res.push_back(i); } return res;
/** * 30. Substring with Concatenation of All Words * * @author Administrator * * 题意:给定一个字符串S和一个字符串数组L,L中的字符串长度都相等, 找出S中所有的子串恰好包含L中所有字符各一次,返回子串的起始位置。 * 该题与leetcode 3.Longest Substring Without Repeating Characters类似 * */ public class Demo1 { /* * 超时边缘的解法:Runtime: 211 ms * 该方法可以通过牛客网,但是在leetcode提交的时候有时候会超时 */ public ArrayList<Integer> findSubstring(String s, String[] words) { ArrayList<Integer> res = new ArrayList<Integer>(); if (s == null || words == null || words.length * words[0].length() > s.length()) return res; //map中的key是字符串,value记录字符串在words中出现的的次数 Map<String,Integer> map=new HashMap<String,Integer>(); Map<String,Integer> tmpMap=new HashMap<String,Integer>(); int wordNum=words.length,wordLen=words[0].length(); //考虑到words中可能会有重读的字符串 for(int i=0;i<wordNum;i++){ if(tmpMap.containsKey(words[i])) tmpMap.put(words[i], tmpMap.get(words[i])+1); else tmpMap.put(words[i], 1); } for(int i=0;i<=s.length()-wordNum*wordLen;i++){ map.clear(); //用空间换时间 int index=i; int count=0; for(int j=0;j<words.length;j++){ String temp=s.substring(index, index+wordLen); if(!tmpMap.containsKey(temp)) break; if(map.containsKey(temp)) map.put(temp, map.get(temp)+1); else map.put(temp, 1); if(map.get(temp)>tmpMap.get(temp)) break; count++; index+=wordLen; } if(count==wordNum) res.add(i); } return res; } }
import java.util.*; public class Solution { /* 将问题分解开(那么需要解决以下几个问题): (1)怎么解决L中单词重复的问题; (2)怎么判断连续的字串是L中的单词 */ public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> list = new ArrayList<>(); if(S.equals("")||S==null||L==null||L.length==0) return list; int len = L.length; int strLen = L[0].length(); int totalLen = len*strLen; int index = 0; int end = index+totalLen; while(index<S.length()&&end<=S.length()){ boolean[] flag = new boolean[len];//布尔数组为了解决L字符串数组中单词重复的问题 int num = 0; for(int i=index;i<end;i+=strLen){ String str = S.substring(i,i+strLen); int j=0; for(;j<len;j++){//不能将判断条件!flag[j]放到循环的判断中,因为一旦条件不符合循环就会退出,不会再继续进行判断 if(!flag[j]&&str.equals(L[j])){ flag[j]=true; num++; break; } } if(j==len) break; } if(num==len) list.add(index); index++; end = index+totalLen; } return list; } }
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { Map<String, Integer> wordMap = new HashMap<>(); for (String item : L) { if (wordMap.containsKey(item)) { wordMap.put(item, wordMap.get(item) + 1); } else { wordMap.put(item, 1); } } ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i <= S.length() - L[0].length() * L.length; i++) { Map<String, Integer> matchMap = new HashMap<>(); for (int matchNum = 0; matchNum < L.length; ) { String word = S.substring(L[0].length() * matchNum + i, L[0].length() * (matchNum + 1) + i); if (!wordMap.containsKey(word)) { break; } else { if (matchMap.containsKey(word)) { matchMap.put(word, matchMap.get(word) + 1); } else { matchMap.put(word, 1); } if (matchMap.get(word) > wordMap.get(word)) { break; } if (++matchNum == L.length) { result.add(i); } } } } return result; } }
vector<int> findSubstring(string S, vector<string> &L) { vector<int>ans; int len = S.size(); int mem = L.size(); if(!mem||!len)return ans; int len_L = L[0].size(); unordered_map<string,int>mp; for(int i=0;i<mem;++i)mp[L[i]]++; for(int i=0;i<=len-len_L*mem;++i){ unordered_map<string,int>mptmp = mp; int cnt = mem; string tmp = S.substr(i,len_L); int j,index = i; for(j=i;j<=len-len_L&&mptmp[tmp];j = j+len_L,tmp =S.substr(j,len_L)){ cnt--; mptmp[tmp]--; } if(cnt==0)ans.push_back(index); } return ans; }
public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> result = new ArrayList<>(); if(S==null||L==null||L.length==0){ return result; } int len = L.length; int wordLen = L[0].length(); for(int i=0;i<wordLen;i++){ ArrayList<String> subList = new ArrayList<>(); for(int j=i;j<S.length()-wordLen+1;j = j+wordLen){ String sub = S.substring(j,j+wordLen); subList.add(sub); } for(int k : findSubstring(subList,L,len)){ result.add(i+k*wordLen); } } result.sort(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1-o2; } }); return result; } private ArrayList<Integer> findSubstring(ArrayList<String> list,String[] L,int size){ ArrayList<Integer> result = new ArrayList<>(); HashMap<String,Integer> map = createMap(L); int left = 0; int count = size; for(int i = 0;i<list.size();i++){ String str = list.get(i); if(!map.containsKey(str)){ while (left<i){ String key = list.get(left); map.put(key,map.get(key)+1); left++; count++; } left = i+1; }else if(map.get(str)==0){ while (!str.equals(list.get(left))){ String key = list.get(left); map.put(key,map.get(key)+1); left++; count++; } left++; }else { map.put(str, map.get(str) - 1); count--; if (count == 0) { result.add(left); String key = list.get(left); map.put(key,map.get(key)+1); left ++; count ++; } } } return result; }
class Solution {
public:
vector<int> out;
map<string,int> book;
vector<int> findSubstring(string S, vector<string> &L) {
out.clear();
book.clear();
if(S.empty()||L.empty())
return out;
int sz=L.size();
int l1=S.length();
int l2=L[0].length();
int l=sz*l2;
for(int i=0;i<sz;i++)
{
if(book.find(L[i])==book.end())
book[L[i]]=0;
book[L[i]]++;
}
for(int i=0;i<=l1-l;i++)
{
map<string,int> bookt=book;
string tm=S.substr(i,l);
int cnt=0;
for(int j=0;j<l;)
{
string tp=tm.substr(j,l2);
j+=l2;
if(bookt.find(tp)==bookt.end())
break;
bookt[tp]--;
if(bookt[tp]<0)
break;
cnt++;
}
if(cnt==sz)
out.push_back(i);
}
return out;
}
};
import java.util.*; public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> list = new ArrayList<>(); int interval = L[0].length(); Map<String, Integer> map = new HashMap<>(); for(int i = 0; i < interval; i++){ map.clear(); for(String s1 : L){ map.put(s1, map.getOrDefault(s1, 0) + 1); } int left = i; int right = i; int counter = map.size(); for(right = i; right <= S.length() - interval; right += interval){ String word = S.substring(right, right + interval); if(map.containsKey(word)){ map.put(word, map.get(word) - 1); if(map.get(word) == 0) counter--; } if(right - left == L.length * interval){ String temp = S.substring(left, left + interval); if(map.containsKey(temp)){ map.put(temp, map.get(temp) + 1); if(map.get(temp) == 1) counter++; } left += interval; } if(counter == 0 && right - left == (L.length - 1) * interval){ list.add(left); } } } Collections.sort(list); return list; } }
import java.util.ArrayList; public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> r = new ArrayList<Integer>(); if(S == null || S.length() == 0 || L.length == 0 || S.length() < L.length * L[0].length()) return r; ArrayList<String> t = new ArrayList<>(); for(int i = 0;i < L.length;i++) t.add(L[i]); for(int i = 0;i <= S.length() - L[0].length();i++){ String tmp = S.substring(i,i+L[0].length()); ArrayList<String> t1 = new ArrayList<>(t); if(t1.contains(tmp)) { t1.remove(tmp); for(int k = i+L[0].length();k <= S.length() - L[0].length();k += L[0].length()){ tmp = S.substring(k,k+L[0].length()); if(t1.contains(tmp)){ t1.remove(tmp); } else break; } if(t1.size() == 0) r.add(i); } } return r; } }
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { int len = S.length(); int n = L.size(); vector<int> result; if(len == 0 || n == 0) return result; int sublen = L[0].length(); int templen = n*sublen; if(len < templen) return result; for(int i = 0;i <= len - templen;i++){ map<string,int> index; bool flag = true; for(int j = 0; j < n;j++){ index[S.substr(i+j*sublen,sublen)]++; // index.insert(make_pair(S.substr(i+j*sublen,sublen),1)); } for(auto t:L){ if(index.find(t) == index.end()){ flag = false; break; }else{ if(index[t] == 0){ flag = false; break; }else{ index[t]--; } } } if(flag) result.push_back(i); } return result; } };
1)先对L中的所有元素做个统计,定义一个hash map<string, int> 型 变量total,统计每个词出现的次数, 另外定义一个同类型的count,用来记录到目前为止,已经找到的L中的元素情况, 当全部找全的时候就找到了一个合法的起始点。然后将count清空,继续找。 2)整体的框架与传统的字符串匹配一致,不同的是这里不要求顺序,所以似乎在S中不能加速移动 import java.util.*; public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> list = new ArrayList<>(); if(S.length()==0||L.length==0){ return list; } int len = L[0].length(); int alllen = L.length*len; HashMap<String,Integer> map = new HashMap<String,Integer>(); for(int i = 0;i<L.length;i++){ if(map.containsKey(L[i])){ map.put(L[i],map.get(L[i])+1); }else{ map.put(L[i],1); } } HashMap<String, Integer> count = null; for(int i =0;i<=S.length()-alllen;i++){ int j = i; int cur = 0; count = new HashMap<String,Integer>(); for(;cur<L.length;cur++){ String sub = S.substring(j,j+len); if(!map.containsKey(sub)){ break; } if(count.containsKey(sub)){ if(count.get(sub)<map.get(sub)){ count.put(sub,count.get(sub)+1); }else{ break; } }else{ count.put(sub,1); } j = j+len; } if(cur == L.length) { list.add(i); } } return list; } }
import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> list=new ArrayList<>();
HashMap<String,Integer> dict=new HashMap<>();
HashMap<String,Integer> result=new HashMap<>();
int m=L.length;
int n=L[0].length();
int len=S.length();
for(String ss:L){
if(!dict.containsKey(ss)){
dict.put(ss,1);
}else{
dict.put(ss,dict.get(ss)+1);
}
}
for(int i=0;i<=len-m*n;++i){
result.clear();
int j;
for( j=0;j<m;++j){
int k=i+j*n;
String str=S.substring(k,k+n);
if(!dict.containsKey(str))
break;
if(result.containsKey(str)){
result.put(str,result.get(str)+1);
}else{
result.put(str,1);
}
if(result.get(str)>dict.get(str))
break;
}
if(j==m)
list.add(i);
}
return list;
}
}