To solve this problem, we need to find all starting indices of substrings in a given string s that are concatenations of every word in the list words exactly once. Each word in the list is of the same length.

Approach

1. Edge Cases Handling: If the input string s is empty or the list words is empty, return an empty list. If the length of s is less than the total length of all words combined, return an empty list.
2. Frequency Map: Create a frequency map of the words in the list words to keep track of the count of each word.
3. Sliding Window Technique: For each starting position (remainder) modulo the length of the words, use a sliding window to check substrings. The window slides in steps equal to the length of the words.
4. Check Valid Substrings: For each window, maintain a current frequency map of the words in the window. If the current frequency map matches the target frequency map, the starting index of the window is a valid result.

Solution Code

from collections import Counter

def findSubstring(s, words):
    if not words or not s:
        return []

    word_len = len(words[0])
    num_words = len(words)
    total_len = word_len * num_words

    if len(s) < total_len:
        return []

    target = Counter(words)
    result = []

    for r in range(word_len):
        left = r
        current = Counter()
        matched = 0

        for i in range(r, len(s) - word_len + 1, word_len):
            current_word = s[i:i+word_len]

            if current_word in target:
                current[current_word] += 1
                if current[current_word] == target[current_word]:
                    matched += 1
            else:
                # Reset if current word is not in target
                current.clear()
                matched = 0
                left = i + word_len
                continue

            # Shrink the window if it exceeds the number of words
            while (i - left) // word_len + 1 > num_words:
                left_word = s[left:left+word_len]
                if left_word in target:
                    if current[left_word] == target[left_word]:
                        matched -= 1
                    current[left_word] -= 1
                    if current[left_word] == 0:
                        del current[left_word]
                left += word_len

            # Check if all words are matched
            if matched == len(target):
                result.append(left)

    return result

Explanation

1. Frequency Map: The target frequency map (target) stores the count of each word in the list words.
2. Sliding Window: For each remainder r (from 0 to word_len-1), we start the window at r and slide it in steps of word_len. This ensures we cover all possible starting positions for valid substrings.
3. Current Frequency: The current frequency map (current) keeps track of the words in the current window. If a word in the window is not in the target map, we reset the window.
4. Shrink Window: If the window size exceeds the number of words in the list, we shrink the window from the left and adjust the current frequency map.
5. Valid Substring: When the current frequency map matches the target map, the starting index of the window is added to the result list.

This approach efficiently checks all possible valid substrings with a time complexity of O(N) (where N is the length of the string s), making it optimal for large inputs. The use of frequency maps and sliding window ensures that we only process each character a constant number of times.

作者声明:本文包含人工智能生成内容。