C++实现LeetCode(211.添加和查找单词-数据结构设计)

[LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计

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.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

LeetCode出新题的速度越来越快了，有点跟不上节奏的感觉了。这道题如果做过之前的那道 Implement Trie (Prefix Tree) 实现字典树(前缀树)的话就没有太大的难度了，还是要用到字典树的结构，唯一不同的地方就是search的函数需要重新写一下，因为这道题里面'.'可以代替任意字符，所以一旦有了'.'，就需要查找所有的子树，只要有一个返回true，整个search函数就返回true，典型的DFS的问题，其他部分跟上一道实现字典树没有太大区别，代码如下：

class WordDictionary {
public:
    struct TrieNode {
    public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for (auto &a : child) a = NULL;
        }
    };

    WordDictionary() {
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *p = root;
        for (auto &a : word) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return searchWord(word, root, 0);
    }

    bool searchWord(string &word, TrieNode *p, int i) {
        if (i == word.size()) return p->isWord;
        if (word[i] == '.') {
            for (auto &a : p->child) {
                if (a && searchWord(word, a, i + 1)) return true;
            }
            return false;
        } else {
            return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1);
        }
    }

private:
    TrieNode *root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

讨论：这道题有个很好的Follow up，就是当搜索的单词中存在星号怎么搞，星号的定义和Wildcard Matching中一样，可以代表任意的字符串，包括空字符串，请参见评论区1楼。

类似题目：

Implement Trie (Prefix Tree)

Wildcard Matching

参考资料：

https://leetcode.com/discuss/36246/my-java-trie-based-solution

到此这篇关于C++实现LeetCode(211.添加和查找单词-数据结构设计)的文章就介绍到这了,更多相关C++实现添加和查找单词-数据结构设计内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • C++实现LeetCode(202.快乐数)

    [LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • C++实现LeetCode(207.课程清单)

    [LeetCode] 207. Course Schedule 课程清单 There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(199.二叉树的右侧视图)

    [LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1     

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) 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&

  • C++实现LeetCode(198.打家劫舍)

    [LeetCode] 198. House Robber 打家劫舍 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

  • C++实现LeetCode(211.添加和查找单词-数据结构设计)

    [LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计 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 c

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode(241.添加括号的不同方式)

    [LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式 Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Exampl

  • C++利用std::forward_list查找插入数据方法示例

    std::forward_list介绍 std::forward_list是在C++11中引入的单向链表或叫正向列表.forward_list具有插入.删除表项速度快.消耗内存空间少的特点,但只能向前遍历.与其它序列容器(array.vector.deque)相比,forward_list在容器内任意位置的成员的插入.提取(extracting).移动.删除操作的速度更快,因此被广泛用于排序算法.forward_list是一个允许在序列中任何一处位置以常量耗时插入或删除元素的顺序容器(seque

  • MySQL根据某一个或者多个字段查找重复数据的sql语句

    sql 查出一张表中重复的所有记录数据 1.表中有id和name 两个字段,查询出name重复的所有数据 select * from xi a where (a.username) in (select username from xi group by username having count(*) > 1) 2.查询出所有数据进行分组之后,和重复数据的重复次数的查询数据,先列下: select count(username) as '重复次数',username from xi group

  • Springboot添加jvm监控实现数据可视化

    1.简介 最近越发觉得,任何一个系统上线,运维监控都太重要了.本文介绍Prometheus + Grafana的方法监控Springboot 2.X,实现美观漂亮的数据可视化. 2.添加监控 Spring-boot-actuator module 可帮助您在将应用程序投入生产时监视和管理应用程序.您可以选择使用 HTTP 端点或 JMX 来管理和监控您的应用程序.Auditing, health, and metrics gathering 也可以自动应用于您的应用程序.引入依赖如下: <!--

  • js如何查找json数据中的最大值和最小值方法

    目录 js查找json数据中的最大值和最小值 使用Math对象来获取最大值和最小值 使用for循环来获取最大值和最小值 获取最大值和最小值返回对应的json数据 用reduce()获取JSON中某个字段值最大的项 需求 语法 返回值 回调函数语法 总结 js查找json数据中的最大值和最小值 js操作数组的方式有很多种,查找json数据中的最大值和最小值也是经常用到,那么接下来就介绍2种方式来实现. 先准备好json数据,根据数组中的age值比较大小: var array = [     {na

  • 利用golang的字符串解决leetcode翻转字符串里的单词

    利用golang的字符串解决leetcode翻转字符串里的单词

    题目 给定一个字符串,逐个翻转字符串中的每个单词. 示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 示例 3: 输入: "a good example" 输出: "exampl

  • JavaScript实现添加、查找、删除元素

    代码很简单,这里就不多废话了. <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>测试文件</title> <style> .reply { width: 500px; height: 100%; overflow: hidden; background-color:#CCC; margin-top: 10px; } .infoAre

  • js动态添加删除,后台取数据(示例代码)

    环境描述:就像你一般在论坛上发表文章,可能带附件,附件的数量是你手动添加删除的!!/*************************************************************************** 添加审批表单模板************************************************************************/// 增长的索引var itemIndex = 1000;// 数量var counter = 0;/

随机推荐