LeetCode Java First 400 문제 풀이 - 030

Substring with Concatenation of All Words    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.
For example, given:s:  "barfoothefoobarman" words:  ["foo", "bar"]
You should return the indices:  [0,9] . (order does not matter).

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

    if (words.length == 0 || words[0].length() == 0)

        return new ArrayList<>();

    HashMap map = new HashMap<>();

    for (String word : words)

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

    List list = new ArrayList<>();

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

    int nlen = words.length * gap;

    for (int k = 0; k < gap; k++) {

        HashMap wordmap = new HashMap<>(map);

        for (int startIndex = k, shift = 0; startIndex < s.length() - nlen + 1

                && startIndex + shift <= s.length() - gap; ) {

            String temp = s.substring(startIndex + shift, startIndex + shift + gap);

            if (wordmap.containsKey(temp)) {

                wordmap.put(temp, wordmap.get(temp) - 1);

                if (wordmap.get(temp) == 0)

                    wordmap.remove(temp);

                if (wordmap.isEmpty())

                    list.add(startIndex);

                shift += gap;

            } else {

                if (shift == 0)

                    startIndex += gap;

                else {

                    wordmap.put(s.substring(startIndex, startIndex + gap),

                            wordmap.getOrDefault(s.substring(startIndex, startIndex + gap), 0)

                                    + 1);

                    startIndex += gap;

                    shift -= gap;

                }

            }

        }

    }

    return list;

}

  ：    。       ，        （      startIndex   shift        ），        ，       -1，     0       ，      ，      。          ，           ，         。