30. Substring with Concatenation of All Words.md

30. Substring with Concatenation of All Words

Thinking:

• Method1: Map, double pointers

1. 首先我想到的是通过构造所有可能的substring。
2. 实际上应该先通过创建map存储单词出现的次数，再通过双指针遍历字符串。

	class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null || words == null || words.length == 0) return result;
        Map<String, Integer> compare = new HashMap<>();
        int totalLen = 0;
        int maxLen = 0;
        for(String ss : words){
            compare.put(ss, compare.containsKey(ss)?(compare.get(ss) + 1):1);
            totalLen += ss.length();
            maxLen = Math.max(maxLen, ss.length());
        }
        int slow = 0; int fast = 0;int start = 0;
        int len = s.length();
        for(; slow <= len - totalLen; slow ++){
            start = slow;
            fast = start + 1;
            Map<String, Integer> temp = new HashMap<>();
            int count = 0;
            for(; fast <= slow + totalLen && fast <= len; fast++){
                String sub = s.substring(start, fast);
                if(!compare.containsKey(sub)){
                    count ++;
                    if(count == maxLen)
                        break;
                    continue;
                }
                else{
                    count = 0;
                    temp.put(sub, temp.containsKey(sub)?(temp.get(sub) + 1):1);
                    if(temp.equals(compare)){
                        result.add(slow);
                        break;
                    }
                    start = fast;
                }
            }
        }
        return result;
    }
}

• 好像题目中提出所有的子字符都是等长的

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null || words == null || words.length == 0) return result;
        Map<String, Integer> compare = new HashMap<>();
        int wordLen = words[0].length();
        int wordNum = words.length;
        for(String ss : words){
            compare.put(ss, compare.containsKey(ss)?(compare.get(ss) + 1):1);
        }
        int slow = 0; int fast = 0;int start = 0;
        int len = s.length();
        for(; slow <= len - wordLen * wordNum; slow++){
            start = slow;
            fast = 1;
            Map<String, Integer> temp = new HashMap<>();
            for(; start + wordLen <= len; fast++ ){
                String sub = s.substring(start, wordLen + start);
                if(!compare.containsKey(sub)){
                    break;
                }
                else{
                    temp.put(sub, temp.containsKey(sub)?(temp.get(sub) + 1):1);
                    if(temp.equals(compare)){
                        result.add(slow);
                        break;
                    }
                    start += wordLen;
                }
            }
        }
        return result;
    }
}