[LeetCode] 30. Substring with Concatenation of All Words

30. Substring with Concatenation of All Words

Hard

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

 

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

 

Constraints:

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] consist of lowercase English letters.

---

문제 풀이

문제 접근

1. 문장의 길이와 단어들의 길이 그리고 단어들을 가진 리스트의 길이의 최대값은 N^2 의 시간복잡도를 가져도 풀릴 듯하다.

풀이

1. words 들안에 들어 있는 단어들이 s 문장의 선택된 인덱스부터 모두 포함하는지 확인해야한다.
2. s 문장에서 words 에 들어있는 단어들이 중복될 수 있기 때문에 words 의 각각 개수가 필요하다.
3. words 의 단어 갯수를 이용하여 s 문장에 얼마나 포함되어 있는지 확인한다.
4. s 안에 들어있는 단어들의 갯수를 확인하면서 답을 구해야하기 때문에, words 의 단어들의 총 갯수와 비교하여 정답을 만든다.

소스 코드

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        hashmap_cnt = Counter(words)
        res = set()
        word_n = len(words[0])
        words_n = len(words)
        sub_n = word_n * words_n
        s_n = len(s)
        def check(index):
            remain = hashmap_cnt.copy()
            words_used = 0
            for j in range(index, index + sub_n, word_n):
                temp = s[j : j + word_n]
                if remain[temp] > 0:
                    remain[temp] -= 1
                    words_used += 1
                else:
                    break
            return words_used == words_n
        
        res = []
        for i in range(s_n - sub_n + 1):
            if check(i):
                res.append(i)
        return res