2. Tries 알고리즘

Trie 알고리즘

- 빠른 문자열 검색 자료구조

- Tree 형태로 각 단어를 저장.

words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]

head, head_rev = {},{}
lengths = []

def tries(head, word):
    node = head # 포인터 지정
    for w in word:
        if w not in node:
            node[w]={}
        node = node[w] # 포인터 이동
        if 'len' not in node:
            node['len'] = [len(word)]
        else:
            node['len'].append(len(word))
    node['end']=True # 각 단어의 끝을 표시

for word in words:
    tries(head,word)
    tries(head_rev,word[::-1])
    lengths.append(len(word))

 

f - r - o - d - o

           - n - t

           - s - t

           - z - e - n

       - r - a - m - e

k - a - k - a - o

 

이렇게 저장됨을 확인할 수 있다.

**dictionary의 key:value에서 value로 다시 dictionary를 선언함. 이때 포인터가 이동하는 모습을 잘 이해하자

 

 

예시: ["foul ", "four ", “fight“, “f”]

출처: https://velog.io/@hope1213/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%82%AC%EA%B2%80%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC