索引所有子串

My idea is pretty simple. Just build a map for the words and their relative count in L. Then we traverse through S to check whether there is a match.

public static List<Integer> findSubstring(String S, String[] L) {
    List<Integer> res = new ArrayList<Integer>(); if (S == null || L == null || L.length == 0) return res; int len = L[0].length(); // length of each word Map<String, Integer> map = new HashMap<String, Integer>(); // map for L for (String w : L) map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1); for (int i = 0; i <= S.length() - len * L.length; i++) {
        Map<String, Integer> copy = new HashMap<String, Integer>(map); for (int j = 0; j < L.length; j++) { // checkc if match String str = S.substring(i + j*len, i + j*len + len); // next word if (copy.containsKey(str)) { // is in remaining words int count = copy.get(str); if (count == 1) copy.remove(str); else copy.put(str, count - 1); if (copy.isEmpty()) { // matches res.add(i); break;
                }
            } else break; // not in L }
    } return res;
}

At first I was gonna to use a set for words. Owing to the fact that duplicate is allowed in L, we need to use map instead.

//字符串的模式匹配变型 
/*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;
    }
}