首页 > itarticle > leetcode 30. substring with concatenation of all words

leetcode 30. substring with concatenation of all words

admin 11月 12, 2020 0

30. Substring with Concatenation of All Words

Difficulty: Hard

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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution

Language: Java

class  {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || s.length() == 0 || words.length == 0) {
            return result;
        }
        int len = words[0].length();
        int totalLen = words.length * len;
        if (s.length() < totalLen) {
            return result;
        }
        Map<String, Integer> countMap = new HashMap<>();
        Map<String, Integer> tmpMap = new HashMap<>();
        for (String word : words) {
            countMap.put(word, countMap.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < s.length() - totalLen + 1; i++) {
            copyMap(countMap, tmpMap);
            for (int j = i; j < i + totalLen; j += len) {
                String tmpStr = s.substring(j, j + len);
                if (!tmpMap.containsKey(tmpStr)) {
                    break;
                } else if (tmpMap.get(tmpStr) == 1){
                    tmpMap.remove(tmpStr);
                } else {
                    tmpMap.put(tmpStr, tmpMap.get(tmpStr) - 1);
                }
            }
            if (tmpMap.isEmpty()) {
                result.add(i);
            }
        }
        return result;
    }
    
    private void copyMap(Map<String, Integer> countMap, Map<String, Integer> tmpMap) {
        for (String key : countMap.keySet()) {
            tmpMap.put(key, countMap.get(key));
        }
    }
}