[leetCode - Trie / Java] 208. Implement Trie (Prefix Tree)

Trie

---

원하는 원소를 찾기 위해 자주 이용되는 방법으로는 BST(Binary Search Tree)가 있다. Trie는 트리의 일종으로 문자열의 키를 효율적으로 저장하고 빠르게 검색하기 위한 자료구조이다.

트라이의 중요한 속성 중 하나는, 루트에서부터 하위 경로까지 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다는 것이다.

1. 문제

---

- 주어진 단어를 Trie에 삽입, 검색, 접두사 시작 확인 메서드를 구현하라

2. 의사 코드

---

한 번에 세 개의 메서드를 구현해야 했다. 메서드를 구현하기 전에 입력받은 문자열의 매 문자들을 노드로 저장하기 위한 설계가 필요해 보인다.

Trie 객체를 초기화하면 root 변수는 생성자를 통해 map, inEnd 속성을 갖는다.
public class Trie {
      private final Node root;

    public Trie() {
        this.root = new Node();
    } // Trie 생성자

  public class Node {
      private HashMap<Character, Node> map; // 문자열의 문자 -> 키값
      private boolean isEnd;

      public Node() {
          this.map = new HashMap<>();
          this.isEnd = false;
      } // Node 생성자
  } // Node class

} // Trie class

-----

    public void insert(String word) {
        // 문자열 word의 문자 하나씩 map에서 확인하여 새롭게 저장.
         for(Character w : word.toCharArray()) {
            if root의 map에 w가 존재하지 않는다면 map에 w를 키값으로 새로운 노드 저장
        }
        isEnd = true; // 문자 끝
    }

    public boolean search(String word) {
        for(word의 길이만큼 반복문,) {
            char c = word.charAt(i);
            map에서 c를 키값으로 꺼내와 노드에 저장 
        } 
    }

    public boolean startsWith(String prefix) {
        search와 비슷하게 시작한다.
        접두사로 시작하는 단어가 트리에 있는지 확인
    }

3. 시도

---

class Trie {
    private final Node root;

    public Trie() {
        this.root = new Node();    
    }

    public class Node {
        private HashMap<Character, Node> map;
        private boolean isEnd;

        public Node() {
            this.map = new HashMap<>();
            this.isEnd = false;
        }
    }

    public void insert(String word) {
        Node current = this.root;
        // System.out.println("word = " + word);
        // System.out.println();
        for(Character w : word.toCharArray()) {
            // System.out.println("w = " + w);
            if(!current.map.containsKey(w)) {
                current.map.put(w, new Node());
            }
            current = current.map.get(w);
            // System.out.println(current);
            // System.out.println(current.isEnd);
            // System.out.println(current.map.get(w));
            // System.out.println();
        }
        current.isEnd = true;
    }

     public boolean search(String word) {
        Node current = this.root;
        for(int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            Node child = current.map.get(c);

            if (child == null) return false;
            current = child;
        }
        return current.isEnd;
     }

     public boolean startsWith(String prefix) {
         Node current = this.root; // 한 글자의 노드
        for(int i=0; i<prefix.length(); i++) {
            char c = prefix.charAt(i); // 한글 자
            // System.out.println("c = " + c);
            current = current.map.get(c);
            // System.out.println("current = " + current);

            if(current == null) {
                return false;
            }
        }
         return true;
     }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

아래는 입력받은 문자열 word을 갖고있는 문자가 map에 있는지 확인하여 전체 List로 반환시킬 수 있다. 예를 들어 hello와 hell이라는 문자열을 insert하고 startsWith("he") 메서드를 호출하면 he를 포함하고 있는 모든 문자가 담긴 List를 반환한다.

public List<String> startsWith(String word) {
        return startsWith(root, new StringBuilder(), word, new HashSet<>());
    }

    public List<String> startsWith(Node node, StringBuilder builder, String word, Set<String> results) {
        if(node.isEnd) {
            String currentWord = builder.toString();
            boolean containsAllChars = true;
            for(char w : word.toCharArray()) {
                if(!currentWord.contains(String.valueOf(w))) {
                    containsAllChars = false;
                    break;
                }
            }
            if(containsAllChars) {
                results.add(currentWord);
            }
        }
        for(Map.Entry<Character, Node> entry : node.map.entrySet()) {
            builder.append(entry.getKey());
            startsWith(entry.getValue(), builder, word, results);
            builder.deleteCharAt(builder.length()-1);
        }
        return new ArrayList<>(results);
    }