LeetCode 솔루션 분류
[8/13] 30. Substring with Concatenation of All Words
본문
Hard
28892123Add to ListShareYou 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
andwords[i]
consist of lowercase English letters.
Accepted
295,079
Submissions
984,832
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 594 ms, faster than 58.12% of Python3 online submissions for Substring with Concatenation of All Words.
Memory Usage: 14.2 MB, less than 77.75% of Python3 online submissions for Substring with Concatenation of All Words.
Memory Usage: 14.2 MB, less than 77.75% of Python3 online submissions for Substring with Concatenation of All Words.
import collections
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not words: return []
word_size = len(words[0])
num_words = len(words)
list_size = num_words * word_size
word_counter = collections.Counter(words)
res = []
for i in range(len(s) - list_size + 1):
word_dic = dict(word_counter)
count = 0
for j in range(i, i+list_size, word_size):
sub_word = s[j:j+word_size]
if sub_word in word_dic and word_dic[sub_word]>0:
word_dic[sub_word] -= 1
count += 1
else: break
if count == num_words: res.append(i)
return res