[关闭]
@Yano 2019-09-20T02:55:54.000000Z 字数 2127 阅读 3795

LeetCode之Trie题目汇总

LeetCode

公众号

coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping


LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总


文章目录:


Implement Trie (Prefix Tree)

Implement a trie with insertsearch, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.


  1. class TrieNode {
  2. boolean isLeaf;
  3. char c;
  4. HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  5. // Initialize your data structure here.
  6. public TrieNode() {
  7. }
  8. public TrieNode(char c) {
  9. this.c = c;
  10. }
  11. }
  12. public class Trie {
  13. private TrieNode root;
  14. public Trie() {
  15. root = new TrieNode();
  16. }
  17. // Inserts a word into the trie.
  18. public void insert(String word) {
  19. HashMap<Character, TrieNode> children = root.children;
  20. for (int i = 0; i < word.length(); i++) {
  21. char c = word.charAt(i);
  22. TrieNode t;
  23. if (children.containsKey(c)) {
  24. t = children.get(c);
  25. } else {
  26. t = new TrieNode(c);
  27. children.put(c, t);
  28. }
  29. children = t.children;
  30. if (i == word.length() - 1) {
  31. t.isLeaf = true;
  32. }
  33. }
  34. }
  35. // Returns if the word is in the trie.
  36. public boolean search(String word) {
  37. HashMap<Character, TrieNode> children = root.children;
  38. for (int i = 0; i < word.length(); i++) {
  39. char c = word.charAt(i);
  40. if (!children.containsKey(c)) {
  41. return false;
  42. }
  43. if (i == word.length() - 1) {
  44. if (children.get(c).isLeaf == true) {
  45. return true;
  46. }
  47. return false;
  48. }
  49. children = children.get(c).children;
  50. }
  51. // useless
  52. return false;
  53. }
  54. // Returns if there is any word in the trie
  55. // that starts with the given prefix.
  56. public boolean startsWith(String prefix) {
  57. HashMap<Character, TrieNode> children = root.children;
  58. for (int i = 0; i < prefix.length(); i++) {
  59. char c = prefix.charAt(i);
  60. if (!children.containsKey(c)) {
  61. return false;
  62. }
  63. if (i == prefix.length() - 1) {
  64. return true;
  65. }
  66. children = children.get(c).children;
  67. }
  68. // useless
  69. return false;
  70. }
  71. }
  72. // Your Trie object will be instantiated and called as such:
  73. // Trie trie = new Trie();
  74. // trie.insert("somestring");
  75. // trie.search("key");
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注