- 浏览: 173621 次
- 性别:
- 来自: 济南
文章分类
最新评论
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
Note:
You may assume that all words are consist of lowercase letters a-z.
这也是一道用前缀树来解决的题目,做了稍微的变形,多了一个对于' . '的检测,对于如何构造一个前缀树,大家可以参考Implement Trie (Prefix Tree)这篇文章。这道题目的代码如下:
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
Note:
You may assume that all words are consist of lowercase letters a-z.
这也是一道用前缀树来解决的题目,做了稍微的变形,多了一个对于' . '的检测,对于如何构造一个前缀树,大家可以参考Implement Trie (Prefix Tree)这篇文章。这道题目的代码如下:
class TrieNode { boolean isLast; TrieNode[] trieNode; public TrieNode() { trieNode = new TrieNode[26]; isLast = false; } } public class WordDictionary { TrieNode root; public WordDictionary() { root = new TrieNode(); } // Adds a word into the data structure. public void addWord(String word) { TrieNode cur = root; for(char c : word.toCharArray()) { if(cur.trieNode[c - 'a'] == null) cur.trieNode[c - 'a'] = new TrieNode(); cur = cur.trieNode[c - 'a']; } cur.isLast = 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) { TrieNode cur = root; if(root == null) return false; return search(word, cur, 0); } public boolean search(String word, TrieNode cur, int index) { if(cur == null) return false; if(index == word.length()) return cur.isLast; char c = word.charAt(index); if(c == '.') { for(TrieNode node : cur.trieNode) { if(search(word, node, index + 1)) return true; } } else { cur = cur.trieNode[c - 'a']; return search(word, cur, index + 1); } return false; } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 334Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 533Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
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 ...