[leetcode] 916. Word Subsets

 

916. Word Subsets

LeetCode - The World's Leading Online Programming Learning Platform

 

이 문제는 words2 의 모든 문자열이 포함되어 있는 words1 의 문자열을 반환하는 문제이다. (subset)

---

 

나의 시도

이 풀이를 봤을 때 이중 루프 돌며, words1 과 word2 의 hashmap 을 비교하는 것밖에 생각나지 않았다.

참고로 문제 조건이 아래와 같았기 때문에 hashmap 생성에 대한 시간복잡도는 시간복잡도 계산에서 제외했다.

1 <= words1[i].length, words2[i].length <= 10

 

내 풀이를 그림으로 나타내면 아래와 같다.

 

 

결과는 Time Limit Exceeded. (너무 단순한 풀이라 예상은 했다ㅎㅎ)

---

정답 풀이

내 풀이와의 차이점은 words2 에 대한 hashmap 생성 시, 각 알파벳별 최대 빈도수만 저장하는 단 1개의 hashmap 을 생성하는 것이다.

 

생각 흐름 포인트

• words2 에 있는 모든 문자열에 대해 빈도수 검사를 통과해야 "universal string" (문제에서 일컫는) 이다.
• 엇 그럼.. 최대 빈도수만 저장하면 되겠구나! 

 

정답 풀이를 그림으로 나타내면 아래와 같다.