LeetCode 30. Substring with Concatenation of All Words

November 2, 2024

Starting with a hard problem today.

Solution

Copy
1class Solution:
2    def findSubstring(self, s: str, words: List[str]) -> List[int]:
3        lenTotal = len(''.join(words))
4        perms = set()
5        def permutations(head, tail):
6            if not len(head):
7                perms.add(tail)
8            for i in range(len(head)):
9                permutations(head[:i] + head[i+1:], tail + head[i])
10        permutations(words, '')
11
12        result = []
13        for i in range(0, len(s)):
14            if s[i:i+lenTotal] in perms:
15                result.append(i)
16        
17        return result

This solution times out. It has a time complexity of O(n) = n! due to the permutations method.

I'm going to try again using python's itertools.permutations method. However, this lead to an out of memory error. Rethinking the algorithm, we can remove the step where we find all permutations. Instead, we will replace our perms set with a method called validSubstring(substring). This method will use a copy of the list of words, and we will loop through the substring and remove any word occurrences. If we always find a word at each step in our substring, we return True. We improve the efficiency of our algorithm by caching the result of each substring as either validSubstring or invalidSubstring set members. This solution is accepted.

Copy
1import itertools
2
3class Solution:
4    def findSubstring(self, s: str, words: List[str]) -> List[int]:
5        if len(s) < len(''.join(words)):
6            return []
7
8        wordLen = len(words[0])
9        def validSubstring(substring):
10            wordsTemp = words[:]
11            for i in range(0, len(substring), wordLen):
12                currWord = substring[i:i + wordLen]
13                if currWord in wordsTemp:
14                    wordsTemp.remove(currWord)
15                else:
16                    return False
17            return True
18        
19        invalidSubstrings = set()
20        validSubstrings = set()
21        wordsLen = wordLen * len(words)
22        window = s[:wordsLen]
23        res = []
24        if validSubstring(window):
25            validSubstrings.add(window)
26            res.append(0)
27
28        for i in range(wordsLen, len(s)):
29            letter = s[i]
30            window = window[1:]
31            window += letter
32            if window not in invalidSubstrings:
33                if window in validSubstrings or validSubstring(window):
34                    res.append(i - wordsLen + 1)
35                    validSubstrings.add(window)
36                else:
37                    invalidSubstrings.add(window)
38        
39        return res
40```
41The time complexity is O(n) = n * k^2 where k is the number of words. It is k^2 because we loop through k words and the remove operation is O(k) = k.

LeetCode 68. Text Justification

LeetCode 76. Minimum Window Substring