LeetCode [884]: Uncommon Words from Two Sentences

📌 LeetCode [884]: Uncommon Words from Two Sentences

🔗 문제 링크

---

문제 설명 📄

두 개의 문자열 s1과 s2가 주어집니다. 각 문자열은 공백으로 구분된 단어들로 이루어져 있습니다.
s1과 s2에서 한 번만 등장하는 단어를 찾아 리스트로 반환하세요.

---

문제 접근 방식 📋

1. 문자열 분리:
   • split(" ")을 사용해 각 문장을 단어 단위로 나눕니다.
2. 빈도 계산:
   • 두 문장에서 각 단어의 빈도를 dict로 저장합니다.
3. 희소 단어 추출:
   • 빈도가 1인 단어만 결과 리스트에 추가합니다.

---

Solution 💻

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        pattern = dict()
        answer = []

        for s in s1.split(" "):
            if s not in pattern:
                pattern[s] = 1
            else:
                pattern[s] += 1

        for s in s2.split(" "):
            if s not in pattern:
                pattern[s] = 1
            else:
                pattern[s] += 1

        for key, value in pattern.items():
            if value == 1:
                answer.append(key)

        return answer

시간 복잡도 ⏲️

• 문자열 분리: (O(n + m)), (n)과 (m)은 각각 s1과 s2의 길이.
• 빈도 계산: (O(n + m)).
• 결과 리스트 생성: (O(k)), (k)는 결과 리스트의 길이.
• 총 시간 복잡도: (O(n + m)).

공간 복잡도 🗄️

• 단어 빈도 저장 공간: (O(u)), (u)는 모든 고유 단어의 개수.
• 결과 리스트 공간: (O(k)), (k)는 결과 리스트의 길이.
• 총 공간 복잡도: (O(u + k)).

---

리팩토링 🛠️

개선된 코드

from collections import Counter

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        pattern = Counter(s1.split(" ") + s2.split(" "))
        return [key for key, value in pattern.items() if value == 1]

리팩토링 후 시간 복잡도 ⏲️

• 문자열 분리 및 합치기: (O(n + m)).
• Counter 계산: (O(u)), (u)는 모든 고유 단어의 개수.
• 리스트 컴프리헨션: (O(u)).
• 총 시간 복잡도: (O(n + m + u)).

리팩토링 후 공간 복잡도 🗄️

• Counter 사용 공간: (O(u)).
• 결과 리스트 공간: (O(k)).
• 총 공간 복잡도: (O(u + k)).

---