엔지니어 게시판
LeetCode 솔루션 분류

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

컨텐츠 정보

본문

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 oncein 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

관련자료

댓글 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.
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
전체 404 / 10 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 931 명
  • 오늘 방문자 5,523 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0