[Leetcode Top Interview 150] 208. Implement Trie (Prefix Tree)

난이도 : medium

문제링크

• trie (or prefix tree)는 문자열 데이터셋의 키를 저장하거나 가져오는데 효과적인 트리자료구조 이다
  • 맞춤법 체크나 자동완성 기능의 구현에 사용된다
• insert(), search(), startWith() 메서드를 구현하세요

 

1. 접근법

• 문자열들은 문자들의 순차적으로 의존하는 데이터
• 하나의 문자를 노드로 생성함
  • 각 노드는 자식의 정보를 담은 Map 자료구조와 해당 글자까지 단어인지 여부를 가지는 boolean 필드를 가진다
• Trie 자료구조는 트리를 순회하는데 사용하기 위한 Node 타입의 root라는 필드를 가지도록 함
• insert(String word)
  • 파라미터로 받은 word의 부분문자열이 tree에 이미 존재한다면
  • tree에서 부분문자열의 마지막 node를 찾고, 나머지 문자들을 node 뒤에 삽입한다
• search(String word)
  • root 부터 시작하여, word의 맨 앞글자가 node의 children 맵 자료구조의 키로 존재하는지 여부를 반복적으로 체크한다
• startsWith(String prefix)
  • root 부터 시작하여, prefix 마지막까지 노드를 찾는다
  • prefix에서, 모든 서브트리들을 끝까지 방문하면서,
    • 서브트리 방문 중, 하나라도 node의 endOfWord 필드값이 true라면
      • 해당 prefix를 가진 단어가 존재한다
    • 방문 노드의 children인 map 자료구조의 key값이 존재하는지 재귀적으로 체크한다

 

2. 의사코드

public void insert(Node node, String word) {
    if (word의 길이가 0이면) {
    	node는 word의 마지막 단어 노드이다 
        -> 그러므로 node의 endOfWord 필드는 true
        return;
    }
    
    if (node의 자식중에 word의 첫번째 단어가 없다면) {
    	node의 children에 (첫번째 단어, 노드) put
    }
    
    insert(child, word.substring(1));
}

public boolean search(Node node, String word) {
	if (word의 길이가 0이라면) {
    	word의 문자 하나하나를 따라 서브트리의 노드를 모두 방문하였음 
    	-> node.endOfWord 리턴
    }
    
    if (word의 첫번째 단어가 node의 자식중에 없다면) {
    	해당 word는 서브트리에 없음
        -> false 리턴;
    }
    
    return search(node.children.get(word의 첫번째 단어), word.substring(1));
}

public boolean startsWith(String prefix) {
	Node cur = this.root, child;
    for (char c : prefix.toCharArray()) {
    	child = cur.children.get(c);
        
        if (child가 Null이면) {
        	return false;
        }
                
        cur = child;	
    }
    
    return startsWith(cur).stream().anyMatch(b -> b == true);
}

private List<Boolean> startsWith(Node node) {
    List<Boolean> answer = new ArrayList<>();

    Node child;
    for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
        child = entry.getValue();            
        if (child의 endOfWord가 true이면) { 
            answer.add(true); 
        } else {
            answer.addAll(startsWith(child));
        }            
    }

    return answer;
}

 

3. 구현 코드

class Trie {
    class Node {
        private Map<Character, Node> children;
        private boolean endOfWord;

        public Node() {
            this.children = new HashMap<>();
            this.endOfWord = false;
        }
    }

    private Node root;

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        insert(this.root, word);
    }

    private void insert(Node node, String word) {
        if (word.length() == 0) {
            node.endOfWord = true;
            return;
        }

        char c = word.charAt(0);
        Node child = node.children.get(c);
        if (child == null) {
            child = new Node();
            node.children.put(c, child);
        }

        insert(child, word.substring(1));
    }
    
    public boolean search(String word) {
        return search(this.root, word);
    }

    private boolean search(Node node, String word) {
        if (word.length() == 0) {
            return node.endOfWord;
        }

        char c = word.charAt(0);
        Node child = node.children.get(c);
        if (child == null) {
            return false;
        }

        return search(child, word.substring(1));
    }
    
    public boolean startsWith(String prefix) {
        Node cur = this.root, child;

        for (char c : prefix.toCharArray()) {
            child = cur.children.get(c);

            if (child == null) {
                return false;
            }
            
            cur = child;            
        }

        if (cur.children.isEmpty()) {
            return true;    
        }

        return startsWith(cur).stream().anyMatch(b -> b == true);
    }

    private List<Boolean> startsWith(Node node) {
        List<Boolean> answer = new ArrayList<>();
        
        Node child;
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            child = entry.getValue();            
            if (child.endOfWord) { 
                answer.add(true); 
            } else {
                answer.addAll(startsWith(child));
            }            
        }

        return answer;
    }    
}

• insert
  • 이전 방문한 노드와 현재 검색하고자 하는 문자가 맨 앞에 포함된 word의 substring을 재귀적으로 호출
    • word의 substring은 재귀적으로 호출되므로 맨앞글자를 지운 부분문자열을 전달한다
  • word가 "" 이면, node의 endOfWord값을 true로 할당함
    • 이전까지 단어를 모두 추가하여 서브트리를 만들었으며, 마지막까지 온 상태이므로
• search
  • word가 ""이 되었다면 node의 endOfWord값을 리턴한다
  • 이전에 방문한 node의 children에 word의 첫글자가 key로 존재하지 않는다면, 찾고자하는 word 가 존재하지 않으므로 false 리턴
• startsWith
  • root에서 prefix 문자열까지 탐색연산
    • 순차적으로 노드를 방문하면서, node의 children의 key로 prefix의 문자가 존재하지 않다면 prefix 문자열이 존재하지 않는다는 뜻
  • prefix 문자열의 마지막 문자까지 탐색하여 마지막 문자의 node를 얻었다면, 해당 node의 서브트리에서 등록된 단어가 존재하는지 확인하기
    • node의 children 전체를 순회하면서,
      • 현재 child node의 endOfWord 값이 true라면, true를 answer에 집어넣고 리턴
      • 현재 child node의 endOfWord 값이 False라면, 재귀적으로 반복함
  • 전체 결과 배열에서 하나라도 true가 있다면 true를 리턴

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(n) - 모든 노드를 생성해야 함

 

5. 개선점

• 잘 모르겠다. 왜 시간복잡도가 안좋은지..

 

6. 회고

• 다른 풀이를 보아도 비슷하게 풀었다