JAVA Trie(트라이) 연습문제

Trie(트라이)를 이용한 문자열 검색

 

 

아래 문자열 저장한뒤  

to

tea

app

 

검색할 문자열로 검색 (to)

 

 

 

JAVA Trie(트라이) 연습문제 
 
 
 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
 
 
        Trie head = new Trie();
 
        head.insert("to");
        head.insert("tea");
        head.insert("tonight");
 
        if(head.prefixSearch("to")) {
            System.out.println("ooo");
        }
        else {
            System.out.println("xxx");
        }
 
 
    }
}
 
 
class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
 
    public void insert(String s) {
        Map<Character, TrieNode> children = root.getChildren();
 
        for(int i=0; i<s.length(); i++) {
 
            char c = s.charAt(i);
            TrieNode node;
 
            if(children.containsKey(c)) {
                node = children.get(c);
                System.out.println("node");
                System.out.println(node);
            }
            else {
                node = new TrieNode();
                children.put(c, node);
                System.out.println("children");
                System.out.println(children);
            }
 
            children = node.getChildren();
 
            if(i == s.length()-1) {
                node.setLeaf(true);
            }
 
 
 
        }
    }
 
    public boolean prefixSearch(String s) {
        Map<Character, TrieNode> children = root.getChildren();
        boolean flag = true;
        TrieNode node = null;
 
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
 
            if(children.containsKey(c)) {
                node = children.get(c);
                children = node.getChildren();
            }
            else {
                flag = false;
                break;
            }
 
 
        }
 
        return flag;
    }
 
    public boolean search(String tea) {
        return false;
    }
}
 
class TrieNode {
    private Map<Character, TrieNode> children = new HashMap<>();
    private boolean leaf;
 
    public TrieNode() {}
 
    public Map<Character, TrieNode> getChildren() {
        return this.children;
    }
 
    public void setLeaf(boolean leaf) {
        this.leaf = leaf;
    }
 
    public boolean getLeaf() {
        return this.leaf;
    }
 
}