648. Replace Words

문제 링크: https://leetcode.com/problems/replace-words/

 

단어들이 포함된 dictionary와 문장이 주어졌을 때, dictionary 내 단어들을 prefix로 하는 단어들을 prefix로 교체하면 되는 문제. Dictionary 내 단어가 1000개, 각 단어의 길이가 100, 문장 내 최대 단어 개수가 1000개라서 무식하게(?) 2중... 3중 for문으로 풀었다. 일단 통과는 되더라.

	class Solution:
	def replaceWords(self, dictionary: List[str], sentence: str) -> str:
	lst = sentence.split(' ')
	dic = sorted([[x, len(x)] for x in dictionary], key=lambda x: x[1])
	dic = [x[0] for x in dic]
	for i in range(len(lst)):
	for j in range(len(dic)):
	if dic[j] == lst[i][:len(dic[j])]:
	lst[i] = dic[j]
	break
	return ' '.join(lst)

view raw Replace Words.py hosted with ❤ by GitHub

그런데 결국 dictionary 내 단어들이 prefix 역할을 하기 때문에 이걸 좀 더 효율적으로 찾는 알고리즘을 쓰면 더 빠를 수 있겠다! 하는 생각이 들었고, 내 솔루션보다 더 빠른 솔루션들을 찾아보니 역시 trie를 썼더라.

 

...대부분 직접 구현해서 쓰시던데, 어떤 분이 import Trie를 통해서 문제를 푸셨던 것 같다. 죄다 import가 되는 leetcode긴 하지만 이런 것도 import가 되나 싶었는데, 내가 잘못 본 건지 해당 솔루션 링크가 없어서 기억이 나지 않는다.