[LeetCode] 1408. String Matching in an Array

- Problem

1408. String Matching in an Array

문제는 심플하다.
주어진 배열에서 substring을 찾는 문제이다.

- 내 풀이 1

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        answer = []
        
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue
                if words[i] in words[j]:
                    answer.append(words[i])
                    break
                
        return answer

- 결과

easy 난이도이기에 easy스럽게 brute-force로 풀었다.
주어진 배열의 길이도 최대 100이기에 충분히 완전탐색으로 풀 수 있다.
하지만, 시간복잡도 O(N^2)이기에, 더 나은 방법으로 풀 고민을 해봤다.

- 내 풀이 2

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        target_string = " ".join(words)
        answer = []
        
        for word in words:
            if target_string.count(word) >= 2:
                answer.append(word)
        
        return answer

- 결과

O(n)을 만족한다. 시간이 많이 줄은 것을 확인할 수 있다.
아니다. count함수가 배열 전체를 순회하기에 배열의 길이만큼 시간 복잡도가 늘어난다.
따라서, 풀이 2의 코드도 O(n^2)이다.
빌어먹을 리트코드 저지

substring을 구하는 trie가 있긴 하지만... 다음에 유사 문제가 나오면 그때 풀어봐야겠다.
^ㅡ^