Trie的实现

参考HankerRank上的Trie的实现。

import java.util.HashMap;

/**
 * Created by dylan on 10/29/16.
 */
public class Trie {
    public static class Node {
        // Solve 'Contacts' using Tries
        private static final int NUM_OF_CHARACTERS = 26;
//        HashMap<Character, Node> children;
//        boolean isCompleteWord;
        Node[] children = new Node[NUM_OF_CHARACTERS];
        int size = 0;


        private static int getCharIndex(char c) {
            return c - 'a';
        }

        private Node getNode(char c) {
            return children[getCharIndex(c)];
        }

        private void setNode(char c, Node node) {
            children[getCharIndex(c)] = node;
        }

        public void add(String s) {
            add(s, 0);
        }

        private void add(String s, int index) {
            size++;
            if (index == s.length()) return;
            char current = s.charAt(index);
            Node child = getNode(current);
            if (child == null) {
                child = new Node();
                setNode(current, child);
            }
            child.add(s, index + 1);
        }

        public int findCount(String s, int index) {
            if (index == s.length()) return size;
            Node child = getNode(s.charAt(index));
            if (child == null) return 0;
            return child.findCount(s, index + 1);
        }

    }




}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s