首页 > 试题广场 >

索引所有子串

[编程题]索引所有子串
  • 热度指数:7369 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个字符串S和一组单词L,L中单词的长度都相等,找出S中的符合以下要求的子串在S中的起始位置索引:子串为L中所有单词串联在一起(单词的顺序随意),L中的每个单词只出现一次,中间不能有其他的字符。
例如:给定S="nowcoderacodnowert",L为["now", "cod"]
返回的索引应该是[0,9].(不用关心给出索引的顺序)
//一个长度为M(表示单个单词的长度)*N(表示单词数组的长度)的子串在S上从左到右平移,每个位置上,直接去判断是不是每一个L中的单词都出现了一次。
class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
       map<string,int> words;  
        map<string,int> curStr;  
        for(int i = 0; i < L.size(); ++i)  
            ++words[L.at(i)];  
        int N = L.size();  
        vector<int> ret;  
        if(N <= 0)   return ret;  
        int M = L.at(0).size();  
        for(int i = 0; i <= (int)S.size()-N*M; ++i)  
        {  
            curStr.clear();  
            int j = 0;  
            for(j = 0; j < N; ++j)  
            {  
                string w = S.substr(i+j*M, M);  
                if(words.find(w) == words.end())  
                    break;  
                ++curStr[w];  
                if(curStr[w] > words[w])  
                    break;  
            }  
            if(j == N)  ret.push_back(i);  
        }  
        return ret;  
    }  
};
发表于 2016-07-24 15:55:40 回复(0)
更多回答
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;
    }

发表于 2017-07-04 09:58:40 回复(5)
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;
    }
}

发表于 2017-07-31 19:29:48 回复(0)
//说好的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;
    }
}

编辑于 2016-11-03 18:17:40 回复(1)
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;		
    }
};

发表于 2017-09-14 00:45:13 回复(0)
//字符串的模式匹配变型 
/*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; } }

编辑于 2016-08-13 15:46:38 回复(0)
题意:给定一个字符串S和一个字符串数组L,L中的字符串长度都相等,找出S中所有的子串恰好包含L中所有字符各一次,返回子串的起始位置。
思路:
定义一个哈希表count用来记录words的个数;
遍历string的每一个字符s[i],停止条件是当剩余的字符个数少于words中的字符个数:
    定义另一个哈希表seen,用来记录遍历出的子串
    j循环nums次,nums代表words中单词的个数
        取出以i + j * len 为首字符,长度为len的子串,在count中寻找是否存在
        若存在,记录出现的次数,并与count中对比,大于则以 i 开始的子串非法
        若不存在,同样以 i 开始的子串非法
    记录此时的索引 i
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>
发表于 2019-05-26 19:09:59 回复(0)
感觉自己写的很复杂,但是应该思路比较清晰。我们应该用hash_map来保存我们L中的元素,这样可以减少查找复杂度,每次查找完(得到一个完整匹配),都要将hash_map中的值恢复为原值用于下次查找,原因是在查找计数过程中需要更改hash_map中的值,感觉这里可以优化。
    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;

发表于 2018-03-28 11:42:39 回复(0)
/**
 * 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;
	}
}

编辑于 2017-07-20 12:13:27 回复(0)
import java.util.*;

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        Map<String, Integer> map;
        int len = L[0].length(), strLen = len * L.length;
        for (int i = 0; i <= S.length() - strLen; i++) {
            map = new HashMap<>();
            for (int k = 0; k < L.length; k++) {
                if (map.containsKey(L[k]))
                    map.replace(L[k], map.get(L[k]) + 1);
                else
                    map.put(L[k], 1);
            } 
            int cnt = 0, j = i;
            while (cnt < L.length) {
                String word = S.substring(i + len * cnt, i + len * (cnt + 1));
                Integer val = map.get(word);
                if (val == null || val == 0)
                    break;
                else map.replace(word, map.get(word) - 1);
                cnt++;
            }
            if (cnt == L.length)
                res.add(i);
        }
        
        return res;
    }
}
发表于 2020-09-30 10:41:02 回复(0)
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;
    }
}

发表于 2020-06-11 10:59:31 回复(0)
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;
    }
}


发表于 2019-09-25 23:54:06 回复(0)
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;
    }

发表于 2019-08-20 22:42:01 回复(0)
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
    vector<int> result;
    if(S.empty()||L.empty()||S.size()<L[0].size()*L.size())
        return result;
    int sub = L[0].size();
    int lengthS = S.size();
    int len = L.size();

    unordered_map<string,int> dict;
    for(int i=0; i<len; i++){
        dict[L[i]]++;
    }

    for(int i=0; i<lengthS - sub*len+1; i++){
        unordered_map<string,int> seen;
        int j=0;
        for(; j<len; j++){
            string word = S.substr(i+j*sub, sub);
            if(dict.find(word) != dict.end()){
                seen[word]++;
                if(seen[word]>dict[word])
                    break;
            }
            else
                break;
        }
        if(j==len)
            result.push_back(i);
    }
    return result;
}

};
发表于 2019-08-08 21:36:14 回复(0)
 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;

    }
1、因为所有L中所有word都相等,所以可将字符串分割成字符数组 如 barfoothefoobarman
[bar, foo, the, foo, bar, man]
[arf, oot, hef, oob, arm]
[rfo, oth, efo, oba, rma]
2、问题就转换成每个字符串数组中求解
3、将求解结果转换下 i+k*wordLen
4、要求结果从大到小,所以排下序
发表于 2018-08-31 14:41:27 回复(0)
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;
    }
};
发表于 2018-06-23 10:38:58 回复(0)
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;
    }
}


发表于 2018-04-03 11:16:07 回复(0)
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;
    }
}

发表于 2018-03-26 21:42:32 回复(0)
  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;
      }
  };

发表于 2017-07-28 11:27:15 回复(0)
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;
    }      
}
               
               
              
               
               

发表于 2017-06-08 21:32:37 回复(0)
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;
    }
}

发表于 2017-04-14 10:49:06 回复(0)