Substring with Concatenation of All Words 30(LeetCode)

Question

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 words exactly 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).

Solution

这道题思想很简单，就是用HashMap记录words中的信息，再用two pointers遍历s看都没有substring是由words中的所有元素组成的（顺序没关系）。

1. 用HashMap记录所有的words中的元素及其出现的次数

2. 然后用双指针开始遍历string。用一个指针记录起始位置，另一个指针开始以words中元素的长度开始扫描，如果遇到一个不在HashMap中的子字符串或者该子字符串出现的次数大于其在words中出现的次数则暂停，说明以该起始位置为起点的子字符串不能由words中的所有元素组成。

3. 继续下一个起始位置的扫描，重复2。直到某个起始位置到s的结尾的长度比words中所有元素的长度和小时，停止。

代码如下：

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if(s == null || words == null || words.length == 0){
            return res;
        }

        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String str : words){
            if(map.containsKey(str)){
                map.put(str, map.get(str) + 1);
            }else{
                map.put(str, 1);
            }
        }

        int l = words[0].length();
        int len = l * words.length;
        int left, right;
        int count;
        for(left = 0; s.length() - left >= len; left++){
            HashMap<String, Integer> mymap = new HashMap<String, Integer>(map);
            right = left;
            String curt = s.substring(right, right + l);
            count = 0;
            while(mymap.containsKey(curt) && mymap.get(curt) > 0){
                mymap.put(curt, mymap.get(curt) - 1);
                count++;
                right += l;
                if(right >= s.length() || right + l > s.length()){
                    break;
                }
                curt = s.substring(right, right + l);
            }

            if(count == words.length){
                res.add(left);
            }
        }

        return res;
    }
}