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;
    }

}