30. Substring with Concatenation of All Words

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 = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

Solution

(1) Java

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> rst = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return rst;
        }
        int wordLen = words[0].length();
        int totalLen = words.length*wordLen;
        if (s.length() < totalLen) {
            return rst;
        }
        Map<String, Integer> counter = new HashMap<>();
        for (String word : words) {
            counter.put(word, counter.getOrDefault(word, 0)+1);
        }
        for (int i = 0; i < s.length()-totalLen+1; i++) {
            String sub = s.substring(i, totalLen+i);
            Map<String, Integer> map = new HashMap<>();
            int j = 0;
            while (j < totalLen) {
                String word = sub.substring(j, wordLen+j);
                if (!counter.containsKey(word)) {
                    break;
                } 
                map.put(word, map.getOrDefault(word, 0)+1);
                if (map.get(word) > counter.get(word)) {
                    break;
                }
                j += wordLen;
            }
            if (j == totalLen) {
                rst.add(i);
            }
        }
        return rst;
    }
}

(2) Python

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        def getIdxForSubstring(sub, seen):
            if not sub:
                return 1
            word = sub[0:wordLen]
            if not wd.get(word):
                return -1
            seen[word] += 1
            if seen[word] > wd[word]:
                return -1
            return getIdxForSubstring(sub[wordLen:], seen)

        rst = []
        if not s or not words:
            return rst
        wordLen = len(words[0])
        totalLen = len(words)*wordLen
        if len(s) < totalLen:
            return rst
        wd = collections.Counter(words)
        for i in range(len(s)-totalLen+1):
            seen = collections.defaultdict(int)
            idx = getIdxForSubstring(s[i:i+totalLen], seen)
            if idx != -1:
                rst.append(i)
        return rst

(3) Scala