30. Substring with Concatenation of All Words

 一刷 08/2022

Version #1 Sliding Window

感觉这个的重点是sliding window invalid的时候不skip而是一个一个地挪left

Time - word length W, word count N, string length L - outer loop W, inner loop L / W * W(for substring operation), N to initialize the word count map - total O (N + WL)

Space O(NL)

Runtime: 28 ms, faster than 75.86% of Java online submissions for Substring with Concatenation of All Words.

Memory Usage: 54.5 MB, less than 62.97% of Java online submissions for Substring with Concatenation of All Words.

class Solution {

    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> result = new ArrayList<>();

        if (words == null || words.length == 0) {

            return result;

        }

        int wordL = words[0].length();

        int totalL = wordL * words.length;

        Map<String, Integer> map = new HashMap<>();

        for (String word : words) {

            map.put(word, map.getOrDefault(word, 0) + 1);

        }

        for (int i = 0; i < wordL; i++) {

            // start using sliding window

            int left = i, right = i;

            int wordCount = words.length;

            // count of words between [left, right)

            Map<String, Integer> currMap = new HashMap<>();

            while (right + wordL <= s.length()) {

                // expand for one word

                String currWord = s.substring(right, right + wordL);

                right += wordL;

                int currCount = currMap.getOrDefault(currWord, 0) + 1;

                currMap.put(currWord, currCount);

                if (currCount <= map.getOrDefault(currWord, 0)) {

                    wordCount--;

                }

                if (right - left > totalL) {

                    currWord = s.substring(left, left + wordL);

                    left += wordL;

                    currCount = currMap.getOrDefault(currWord, 0) - 1;

                    currMap.put(currWord, currCount);

                    if (currCount < map.getOrDefault(currWord, 0)) {

                        wordCount++;

                    }

                }

                if (wordCount == 0) {

                    result.add(left);

                }

            }

            

        }

        return result;

    }

}