Implement a trie with insert, search, and startsWith methods.
- Example:
- Trie trie = new Trie();
- trie.insert("apple");
- trie.search("apple"); // returns true
- trie.search("app"); // returns false
- trie.startsWith("app"); // returns true
- trie.insert("app");
- trie.search("app"); // returns true
- Note:
- You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.
使用数组保存子节点, 但是不可扩展, 效率高
使用 ArrayList 保存子节点, 可扩展, 但查找效率差
使用 Map 保存子节点
- class Trie { // mytip
- TrieNode root;
- /** Initialize your data structure here. */
- public Trie() {
- root = new TrieNode();
- }
- /** Inserts a Word into the trie. */
- public void insert(String Word) {
- TrieNode cur = root;
- if (null == cur) {
- cur = new TrieNode();
- }
- for (int i = 0; i < Word.length(); i++) {
- char c = Word.charAt(i);
- List < TrieNode > list = cur.children;
- boolean flag = false;
- for (int j = 0; j < list.size(); j++) {
- if (list.get(j).val == c) {
- cur = list.get(j);
- flag = true;
- break;
- }
- }
- if (!flag) {
- TrieNode t = new TrieNode(c);
- cur.children.add(t);
- cur = t;
- }
- }
- cur.isWord = true;
- }
- /** Returns if the Word is in the trie. */
- public boolean search(String Word) {
- TrieNode cur = root;
- for (int i = 0; i < Word.length(); i++) {
- char c = Word.charAt(i);
- if (null == cur || null == cur.children || 0 == cur.children.size()) {
- return false;
- }
- List < TrieNode > list = cur.children;
- boolean flag = false;
- for (int j = 0; j < list.size(); j++) {
- if (list.get(j).val == c) {
- cur = list.get(j);
- flag = true;
- break;
- }
- }
- if (!flag) {
- return false;
- }
- }
- return cur.isWord;
- }
- /** Returns if there is any Word in the trie that starts with the given prefix. */
- public boolean startsWith(String prefix) {
- TrieNode cur = root;
- for (int i = 0; i < prefix.length(); i++) {
- char c = prefix.charAt(i);
- if (null == cur || null == cur.children || 0 == cur.children.size()) {
- return false;
- }
- List < TrieNode > list = cur.children;
- boolean flag = false;
- for (int j = 0; j < list.size(); j++) {
- if (list.get(j).val == c) {
- cur = list.get(j);
- flag = true;
- break;
- }
- }
- if (!flag) {
- return false;
- }
- }
- return true;
- }
- }
- class TrieNode {
- List < TrieNode > children; // 孩子结点使用 List 存放 效率较低
- char val;
- boolean isWord;
- TrieNode() {
- children = new ArrayList < >();
- isWord = false;
- }
- TrieNode(char c) {
- children = new ArrayList < >();
- isWord = false;
- val = c;
- }
- }
- class Trie { //my
- TrieNode root;
- /** Initialize your data structure here. */
- public Trie() {
- root = new TrieNode();
- }
- /** Inserts a Word into the trie. */
- public void insert(String Word) {
- TrieNode cur = root;
- if (null == cur) {
- cur = new TrieNode();
- }
- for (int i = 0; i < Word.length(); i++) {
- char c = Word.charAt(i);
- Map < Character,
- TrieNode > list = cur.children;
- if (list.containsKey(c)) {
- cur = list.get(c);
- } else {
- TrieNode t = new TrieNode(c);
- cur.children.put(c, t);
- cur = t;
- }
- }
- cur.isWord = true;
- }
- /** Returns if the Word is in the trie. */
- public boolean search(String Word) {
- TrieNode cur = root;
- for (int i = 0; i < Word.length(); i++) {
- char c = Word.charAt(i);
- if (null == cur || null == cur.children || 0 == cur.children.size()) {
- return false;
- }
- Map < Character,
- TrieNode > list = cur.children;
- if (list.containsKey(c)) {
- cur = list.get(c);
- } else {
- return false;
- }
- }
- return cur.isWord;
- }
- /** Returns if there is any Word in the trie that starts with the given prefix. */
- public boolean startsWith(String prefix) {
- TrieNode cur = root;
- for (int i = 0; i < prefix.length(); i++) {
- char c = prefix.charAt(i);
- if (null == cur || null == cur.children || 0 == cur.children.size()) {
- return false;
- }
- Map < Character,
- TrieNode > list = cur.children;
- if (list.containsKey(c)) {
- cur = list.get(c);
- } else {
- return false;
- }
- }
- return true;
- }
- }
- class TrieNode {
- Map < Character,
- TrieNode > children; // 使用 map 存放子节点
- char val;
- boolean isWord;
- TrieNode() {
- children = new HashMap < >();
- isWord = false;
- }
- TrieNode(char c) {
- children = new HashMap < >();
- isWord = false;
- val = c;
- }
- }
- LeetCode - 208.Implement Trie(Prefix Tree)
来源: http://www.bubuko.com/infodetail-3008161.html