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.
문제 풀이
문제 접근
- 문장의 길이와 단어들의 길이 그리고 단어들을 가진 리스트의 길이의 최대값은 N^2 의 시간복잡도를 가져도 풀릴 듯하다.
풀이
- words 들안에 들어 있는 단어들이 s 문장의 선택된 인덱스부터 모두 포함하는지 확인해야한다.
- s 문장에서 words 에 들어있는 단어들이 중복될 수 있기 때문에 words 의 각각 개수가 필요하다.
- words 의 단어 갯수를 이용하여 s 문장에 얼마나 포함되어 있는지 확인한다.
- 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