Day031 - 30. Substring with Concatenation of All Words

30. Substring with Concatenation of All Words

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]

Output: [6,9,12]

Explanation:

The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"]. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"]. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

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

내 풀이

from collections import Counter, defaultdict

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        """
        글자의 길이만큼 이동하면서 해시맵으로 확인.
        해시맵은 dict의 set 이용해서 해야되나.. => 중복을 처리못함.

        사용했던 hashmap을 재사용하면서 진행        
        """

        str_len = len(s)
        sub_len = len(words[0])
        words_len = sub_len * len(words)

        answer = []

        words_dict = Counter(words)
            
        for start_idx in range(sub_len): # 단어의 길이만큼 for loop을 돌며 hash map 생성

            # 여기서 만들어진 hash-map을 계속 이용함.
            # words에 있는 글자수*전체 글자수만큼 잘라냄
            check_dict = defaultdict(int)
            for i in range(start_idx, words_len, sub_len):
                add_word = s[i:i+sub_len]
                if add_word in words_dict:
                    check_dict[add_word] += 1

            l, r = start_idx, words_len + start_idx
            while r <= str_len:
                # print(check_dict)
                if check_dict == words_dict:
                    # print("same dict", check_dict, l)
                    answer.append(l)

                sub_word = s[l:l+sub_len]
                add_word = s[r:r+sub_len]
                if check_dict[sub_word] > 1:
                    check_dict[sub_word] -= 1
                else:
                    del check_dict[sub_word]
                check_dict[add_word] += 1
                l += sub_len
                r += sub_len

        return answer        

# Time Complexity : \(O(N)\)