Trie代码java

 

还要判断节点是否是一个映射  比如 pan  pandas 所以需要一个boolen来判断不是叶子结点是否为一个单词

 

211. Add and Search Word - Data structure design

Medium

81251FavoriteShare

Design a data structure that supports the following two operations:

void addWord(word) bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true

 

import java.util.TreeMap;

public class WordDictionary {

    private class Node{

        public boolean isWord;         public TreeMap<Character, Node> next;

        public Node(boolean isWord){             this.isWord = isWord;             next = new TreeMap<>();         }

        public Node(){             this(false);         }     }

    private Node root;

    /** Initialize your data structure here. */     public WordDictionary() {         root = new Node();     }

    /** Adds a word into the data structure. */     public void addWord(String word) {

        Node cur = root;         for(int i = 0 ; i < word.length() ; i ++){             char c = word.charAt(i);             if(cur.next.get(c) == null)                 cur.next.put(c, new Node());             cur = cur.next.get(c);         }         cur.isWord = true;     }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */     public boolean search(String word) {         return match(root, word, 0);     }

    private boolean match(Node node, String word, int index){

        if(index == word.length())             return node.isWord;

        char c = word.charAt(index);

        if(c != '.'){             if(node.next.get(c) == null)                 return false;             return match(node.next.get(c), word, index + 1);         }         else{             for(char nextChar: node.next.keySet())                 if(match(node.next.get(nextChar), word, index + 1))                     return true;             return false;         }     } }

 

实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null 输入: sum("ap"), 输出: 3 输入: insert("app", 2), 输出: Null 输入: sum("ap"), 输出: 5

import java.util.TreeMap;

public class MapSum {

    private class Node{

        public int value;         public TreeMap<Character, Node> next;

        public Node(int value){             this.value = value;             next = new TreeMap<>();         }

        public Node(){             this(0);         }     }

    private Node root;

    /** Initialize your data structure here. */     public MapSum() {

        root = new Node();     }

    public void insert(String key, int val) {

        Node cur = root;         for(int i = 0 ; i < key.length() ; i ++){             char c = key.charAt(i);             if(cur.next.get(c) == null)                 cur.next.put(c, new Node());             cur = cur.next.get(c);         }         cur.value = val;     }

    public int sum(String prefix) {

        Node cur = root;         for(int i = 0 ; i < prefix.length() ; i ++){             char c = prefix.charAt(i);             if(cur.next.get(c) == null)                 return 0;             cur = cur.next.get(c);         }

        return sum(cur);     }

    private int sum(Node node){

        int res = node.value;         for(char c: node.next.keySet())             res += sum(node.next.get(c));         return res;     } }