问题描述

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

For example, given:

s: "barfoothefoobarman"

words: ["foo", "bar"]

You should return the indices: [0,9].

(order does not matter).

 

解决思路

最直观的办法：

1. 用一个boolean[] flag，大小和输入的字符串相同，flag[i]代表s[i...i+lenOfToken]是否在words中；

2. 计算出拼接字符串的长度，然后依次检查是否完全覆盖words（用一个HashMap记录）。

时间复杂度为O(n)，空间复杂度为O(n).

 

注意：words中的word有可能有重复。

 

程序

public class Solution {    public List
     
       findSubstring(String s, String[] words) {		List
      
        res = new ArrayList<>();		if (s == null || s.length() == 0 || words == null || words.length == 0) {			return res;		}                        // 
       
        		HashMap
        
          map = new HashMap
         
          (); 		for (String w : words) {			if (map.containsKey(w)) {				map.put(w, map.get(w) + 1);			} else {				map.put(w, 1);			}		}		int lenOfToken = words[0].length();		int numOfToken = words.length;		int len = s.length();		boolean[] flag = new boolean[len]; // speed up		int i = 0;		while (i + lenOfToken <= len) {			String sub = s.substring(i, i + lenOfToken);			if (map.containsKey(sub)) {				flag[i] = true;			}			++i;		}		int totalLen = lenOfToken * numOfToken;		for (i = 0; i + totalLen <= len; i++) {			if (!flag[i]) {				continue;			}			int k = numOfToken;			int j = i;			HashMap
          
            map_tmp = new HashMap
           
            (map); while (k > 0) { String word_tmp = s.substring(j, j + lenOfToken); if (!flag[j] || !map_tmp.containsKey(word_tmp) || map_tmp.get(word_tmp) == 0) { break; } map_tmp.put(word_tmp, map_tmp.get(word_tmp) - 1); j += lenOfToken; --k; } if (k == 0) { res.add(i); } } return res; }}