[EPI 16.7] The Bedbathandbeyond.com problem

[ami-ryu]

• dictionary
• set of strings
• name

Design an efficient algorithm that checks whether the name isthe concatenation of a sequence of dictionary words

Solution

1) Recursion

• name 으로 시작하는 단어를 사전에서 찾고, 나머지 name 들에 대해서도 찾고 반복
• 단점: 특정 단어에 대해서 high time complexity

2) Cache

• string 의 prefix 들을 캐시의 키로 설정.

3) hash table

• hash table 에 모든 사전들을 저장