`

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.

public class WordDictionary {
    public static class TrieNode {
        TrieNode[] children;
        boolean isLeaf;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    
    private TrieNode root = new TrieNode();
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        if(word == null || word.isEmpty()) return;
        TrieNode node = root;
        for(int i=0; i<word.length(); i++) {
            int j = word.charAt(i)-'a';
            if(node.children[j] == null) {
                node.children[j] = new TrieNode();
            }
            node = node.children[j];
        }
        node.isLeaf = 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) {
        return search(root, word, 0);
    }
    
    private boolean search(TrieNode node, String word, int start) {
        if(node == null) return false;
        if(start == word.length()) return node.isLeaf;
        for(int i=start; i<word.length(); i++) {
            char c = word.charAt(i);
            if(c == '.') {
                for(int j=0; j<26; j++) {
                    if(search(node.children[j], word, i+1)) return true;
                }
                return false;
            } else {
                // node = node.children[c-'a'];
                // if(node == null) return false;
                return search(node.children[c-'a'], word, i+1);
            }
        }
        return false;//node.isLeaf;
    }
}

 

分享到:
评论

相关推荐

    LeetCode 101 - A LeetCode Grinding Guide (C++ Version).rar

    《LeetCode 101 - A LeetCode Grinding Guide (C++ Version)》是一本专为C++程序员设计的深入解析LeetCode算法问题的指南。这本书采用彩色版,以直观的方式讲解了各种数据结构和算法,旨在帮助读者磨练编程技能,...

    c语言-leetcode 0002-add-two-numbers.zip

    c c语言_leetcode 0002_add_two_numbers.zip

    LeetCode---C++实现

    《LeetCode---C++实现》是一本专注于C++编程语言解决LeetCode在线判题平台上的算法问题的书籍。LeetCode是程序员广泛使用的平台,它提供了大量的编程题目来提升编程技能和算法理解,尤其对于准备面试的程序员来说,...

    leetcode1-240题中文题解,md格式,java

    1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...

    leetcode中国-Algorithm-and-Data-Structure:算法与数据结构之道

    leetcode中国算法和数据结构 算法与数据结构之道 我在这个项目中编写了一些数据结构和算法的 C++ 实现。 你可以阅读关于我的中文体验。 顺便说一下,很多链接可能是中文的。 完毕 选择排序 字符串类 插入排序 我尽力...

    java-leetcode-99-recover-binary-search-tree

    java java_leetcode-99-recover-binary-search-tree

    leetcode-leetcode-cli-plugins:leetcode-cli的第3方插件

    leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...

    python-leetcode题解之170-Two-Sum-III-Data-structure-design.py

    针对LeetCode第170题“Two Sum III - Data structure design”,我们首先要掌握的是如何设计一个数据结构来高效地解决两数之和问题。LeetCode 170题要求设计一个数据结构,支持以下操作: 1. add(number):向数据...

    leetcode分类-Data-Structure-and-Algorithm:数据结构与算法

    Data-Structure-and-Algorithm 所用语言 : Java1.8 编辑器 : IntelliJ Idea 此项目主要用于数据结构的复习以及leetcode算法题目练习。 leetcode算法题解位于leetcode/src 文件夹内,按照题目类型进行区分。 数据...

    java-leetcode-105-construct-binary-tree-from-preorder-and-inorde

    java java_leetcode-105-construct-binary-tree-from-preorder-and-inorde

    leetcode2-LeetCode-Solutions-And-Data-Structure-Analysis:用Java实现的LeetCo

    leetcode 2 Java 中的 LeetCode 解决方案 用 Java 实现的 LeetCode 新颖解决方案的集合。 支持你用最简单的方法从易到难解决问题。 解决方案 LeeCode # 问题 困难 源代码 解决方案 1 中等的 1. 散列 O(n) 和 O(n) ...

    LeetCode题解 - Java语言实现-181页.pdf

    13. Two Sum III Data structure design 两数之和III是一个变体的问题,要求设计一个数据结构来解决两数之和问题。可以使用哈希表或树形结构来解决该问题。 ... 资源摘要信息共包含181个LeetCode题解,涵盖了数组...

    离线和leetcode-leetcode-cn-cli:为leetcode-cn.com工作

    leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...

    leetcode2sumc-leetcode-cli:leetcode-cli

    leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...

    leetcode接口-leetcodeHelper:leetcodeHelper

    leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 &gt;=90.0.4430 安装 # Prepare your virtual environment conda ...

    leetcode答案-leetcode--python:leetcode--python

    这个压缩包“leetcode--python”显然包含了与LeetCode相关的Python解题代码,可能是一个开源项目,用于存储用户或社区成员解决LeetCode问题的Python实现。 **LeetCode概述** LeetCode提供了一系列的算法和数据结构...

    离线和leetcode-leetcode-cli-2.6.1:leetcode-cli-2.6.1

    leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...

    leetcode26-algo:算法与数据结构

    leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...

    leetcode答案-Leetcode--Algo:Leetcode-某事

    leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答

    leetcode答案-Data-Structure-and-Algorithms:数据结构与算法

    leetcode 答案 复习资料 一篇文章有的段落没看懂没关系,记下来继续往下看,从其他文章中找答案。文章都是人写的、没经过校对,出现不理解的段落很正常。多读多搜索其他的文章,从其他文章中找问题的解释。 网络基础...

Global site tag (gtag.js) - Google Analytics