그림 이모티콘 표 및 알고리즘

Question

사용자가 문자열을 입력 할 수있는 Android 앱을 만들려고합니다. 해당 문자열과 관련된 목록 그림이 표시됩니다. (Venmo 앱처럼) 예 :

사례 1 : 사용자가 'pizz'를 입력하고 목록에 ''이 표시되면 사용자가 피자가 아니라 'pizz'를 입력합니다. 사례 2 : 사용자가 "rabb"를 입력하고 목록에 ""및 ""이 표시되면 사용자가 토끼가 아닌 "rabb"를 입력합니다.

이 문제에 대한 올바른 데이터 구조 및 알고리즘은 무엇입니까?

Answer 1

trie입니다. Wikipedia

트라이에서, 디지털 트리 때로는 기수 트리 또는 접두사 트리 (그들은 접두사로 검색 할 수있는), 검색 트리 정렬 트리 데이터 구조의 일종이다라고 ..

트라이는 HashMap<K,V>과 유사하므로 키를 사용하여 조회를 수행하고 값을 얻을 수 있습니다. 차이점은 접두어으로 검색 할 수도 있다는 것입니다. 접두어가 주어지면 접두사가있는 구조의 모든 키 - 값 쌍을 찾습니다. 기본적으로 이고 검색 제안을 생성하기위한 데이터 구조는입니다.

일반 아이디어 :

Trie<String, String> t = new Trie<String, String>(); 
t.insert("pizza", ""); 
t.insert("rabbit1", ""); 
t.insert("rabbit2", ""); 
// then later... 
t.findByPrefix("rabb"); // [,] 

불행하게도, 시도 (예를 들어, 자바 컬렉션 프레임 워크 또는 Google 구아바 등) 너무 일반적이며, 모든 인기있는 데이터 구조 라이브러리에 존재하지 않습니다. 직접 구현하거나 기존 구현을 찾아 수정해야합니다. 추천 :

1. 이론을 배우십시오. 이 시계는 video입니다. 기본 사항을 가르쳐 줄 YouTube에 대한 정보가 많이 있습니다. Google에 "N-way trie"를 검색하고 그것에 대한 노트를 읽을 수도 있습니다.
2. 이 클래스를 TrieST으로 가져 와서 수정하십시오. 그것은 당신이 필요로하는 것과 매우 유사합니다. (또는 이미 완벽합니다.) http://algs4.cs.princeton.edu/52trie/TrieST.java.html 구체적으로 keysWithPrefix 방법을보십시오.