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.
For example:
addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true
public class WordDictionary { private Trie trie = new Trie(); // Adds a word into the data structure. public void addWord(String word) { trie.insert(word); } // 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 trie.search(word); } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern"); class Trie { private TrieNode root = new TrieNode(); public void insert(String word) { root.insert(word.toCharArray(), 0); } public boolean search(String word) { return root.search(word.toCharArray(), 0); } } class TrieNode { private TrieNode[] nodes; private boolean end; public TrieNode() { int size = 26; nodes = new TrieNode[size]; end = false; } public void insert(char[] chars, int start) { if (start == chars.length) { end = true; return; } int idx = getIndex(chars[start]); if (idx == -1) { for (int i = 0; i < nodes.length; i++) { insert(i, chars, start); } } else { insert(idx, chars, start); } } private void insert(int i, char[] chars, int start) { // TODO Auto-generated method stub TrieNode node = nodes[i]; if (node != null) { node.insert(chars, start+1); } else { node = new TrieNode(); nodes[i] = node; node.insert(chars, start+1); } } private int getIndex(char c) { // TODO Auto-generated method stub if (c == '.') { return -1; } return c - 'a'; } public boolean search(char[] chars, int start) { if (start == chars.length) { return end; } char c = chars[start]; int idx = getIndex(c); if (idx == -1) { for (int i = 0; i < nodes.length; i++) { boolean flag = search(i, chars, start); if (flag) { return true; } } return false; } else { return search(idx, chars, start); } } private boolean search(int i, char[] chars, int start) { // TODO Auto-generated method stub TrieNode node = nodes[i]; if (node == null) { return false; } return node.search(chars, start + 1); } }
相关推荐
201 | [Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _...
lru缓存leetcode ...数据结构设计https://leetcode.com/problems/add-and-search-word-data-structure-design/ 硬字搜索IIhttps://leetcode.com/problems/word-search-ii/ EasyFind the Difference ...
4) Add the Drag and Drop Component Suite components directory to your library path. 5) Load the demo project group: demo\dragdrop_delphi.bpg for Delphi 5 and 6 demo\dragdrop_bcb4.bpg for C++ ...
(b) the name of the table, the names of the table's attributes, the data types of the table's attributes, the formats of the table's attributes, and the maximum number of rows that the table can have...
Discover how Cassandra's distributed design lets you add or remove nodes from the cluster as your application requires, Get examples for writing clients in Java, Python, and C#, Extend Cassandra by ...
Allows create and fill data in design-time and save data in dfm file of the Form. Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an ...
Allows create and fill data in design-time and save data in dfm file of the Form. Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an ...
Allows create and fill data in design-time and save data in dfm file of the Form. Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an ...
Allows create and fill data in design-time and save data in dfm file of the Form. Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an ...
Allows create and fill data in design-time and save data in dfm file of the Form. Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an ...
Digital Image Structure Cameras and Eyes Television Video Signals Other Image Acquisition and Display Brightness and Contrast Adjustments Grayscale Transforms Warping Chapter 24 - Linear Image ...
Transact-SQL, or T-SQL, is Microsoft Corporation’s powerful implementation of the ANSI standard SQL database query language, which was designed to retrieve, manipulate, and add data to relational ...
The user must be able to add to and modify the design in order to produce the desired result. Additionally, all tools would need a way to save and load designs from disk so that users can ...
Current version allows preview, print and design report template under Windows and Linux platform (qt). + Added Embarcadero RAD Studio XE3 support - fixed compatibility with Fast Report FMX installed...
What structure and design strategies you can use for compelling data visualization How to use data binding, animations and events, scales, and color pickers How to use shapes, path generators, arcs ...
What structure and design strategies you can use for compelling data visualization How to use data binding, animations and events, scales, and color pickers How to use shapes, path generators, arcs ...
structure design 1.7 (653) Two Sum IV - Input is a BST 1.8 (560) Subarray Sum Equals K 概括 对于总和问题, 一般有两种方法:一种是二指针技能,另一种是使用Map 对于两个指针技能,它仅在数组排序时有效,...
Use SQL DDL to add structure to a database, and use DML to manipulate data Define and work with SQLite data types Persist highly structured data for fast, efficient access Master Android classes for ...
Basic Declarations and Expressions Basic Program Structure Simple Expressions The std::cout Output Object Variables and Storage Variable Declarations Assignment Statements Floating-Point Numbers ...
Control the layout structure and design and edit code to control screen events Respond to user interaction using Java and XML with your app Keep your users up to date with Android's new notification ...