LeetCode 솔루션

[8/13] 30. Substring with Concatenation of All Words

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.08.13 10:36

6,064 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

30. Substring with Concatenation of All Words

Hard

28892123Add to ListShare

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.

Accepted

295,079

Submissions

984,832

#Adobe, #Apple, #Oracle, #Amazon, #Microsoft

링크

https://leetcode.com/problems/substring-with-concatenation-of-all-words/ 1460 회 연결

익명
작성일 2022.08.13 10:36

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

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.
[code=Python 3]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[/code]