[leetcode]Substring with Concatenation of All Words

新博文地址：[leetcode]Substring with Concatenation of All Words

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

 这道题，坑爹！！！时间复杂度已经不能再优化了，居然还是过不了，提交了N次啊，N次啊！！！！最后听同学的建议，对细节上进行了优化，其实就是做了一个剪枝（只是减少了常数次检查啊，居然就过了，oj要不要卡的这么紧，哭）

思路是这样的：

从第一个字符完后遍历，每次截取wordLength个长度的子串，看是否是字典中的单词，如不是，startIndice++，继续，如是（记录这个起点下标startIndice），就继续截取下面的wordLength长度。直到->

1. 把字典遍历完了，good，将startIndice加入list中

2. 字典没有遍历完，但是遇到这个子串不是字典单词，则返回，startIndice ++ ，从新开始遍历

代码如下：

   public List<Integer> findSubstring(String S, String[] L) {
    	List<Integer> list = new ArrayList<Integer>();
        if(L == null || L.length == 0 || S.length() < L[0].length()){
        	return list;
        }
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        for(int i = 0 ; i < L.length; i++){
       		map.put(L[i], map.get(L[i]) == null ? 1 : map.get(L[i]) + 1);
        }
        int wordLength = L[0].length();
        boolean firstMatch = true;
        Map<String,Integer> copyMap = ( HashMap<String,Integer> )map.clone();
        for(int startIndice = 0 ,j = 0 ; startIndice <= S.length() - wordLength * L.length && j <= S.length() - wordLength;){
        	String str = S.substring(j, wordLength + j);
        	if(copyMap.containsKey(str) && copyMap.get(str) > 0){
        		if(firstMatch){//第一个单词匹配成功，记录起点下标
        			startIndice = j;
        			firstMatch = false;
        		}
        		copyMap.put(str, copyMap.get(str) - 1);
        		j += wordLength;
        		if(j - startIndice == wordLength * L.length){//如果长度达到了字典的总长度，则匹配成功
        			list.add(startIndice);
        			firstMatch = true;
        		    j = startIndice + 1;
        		    copyMap = ( HashMap<String,Integer> )map.clone();//更新字典，以便重新匹配
        		}
        	}else{
        		if(!firstMatch){
        			j = startIndice + 1;//如果之前匹配了几个单词，但是后面的不匹配，从七点下标后一位开始遍历
        			firstMatch = true;
        			copyMap = ( HashMap<String,Integer> )map.clone();
        		}else{//如果不匹配，遍历下一个字母
        			j++;
        		}
        		startIndice++;
        	}
        }
        return list;
    }

 图中红色标记的是后来修改的剪枝条件，其实对改不改对时间复杂度都没有影响，但是在细节的时间上的确是缩短了一点，就这么一点，卡了我一整天.....还是对细节考虑不周啊，以此为戒吧