面试经典150题——字典树

文章目录

  • 1、实现 Trie (前缀树)
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2、添加与搜索单词 - 数据结构设计
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3、单词搜索 II
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路

对于字典树而言，之前做过类似的教程，详情可以看走入字典树一。

1、实现 Trie (前缀树)

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

1.3 解题代码


class TrieNode{
    TrieNode[] next;
    boolean end;
    TrieNode(){
        next = new TrieNode[26];
        end = false;
    }
}


class Trie {

    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode now = root;
        for(int i = 0; i < word.length(); ++i){
            int child = word.charAt(i) - 'a';
            if(now.next[child] == null){
                now.next[child] = new TrieNode();
            }
            now = now.next[child];
        }
        now.end = true;
    }
    
    public boolean search(String word) {
        TrieNode now = root;
        for(int i = 0; i < word.length(); ++i){
            int child = word.charAt(i) - 'a';
            if(now.next[child] == null){
                return false;
            }
            now = now.next[child]; 
        }
        return now.end;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode now = root;
        for(int i = 0; i < prefix.length(); ++i){
            int child = prefix.charAt(i) - 'a';
            if(now.next[child] == null){
                return false;
            }
            now = now.next[child]; 
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

1.4 解题思路

  1. 字典树经典题型，套用模板即可。

2、添加与搜索单词 - 数据结构设计

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

  • WordDictionary() 初始化词典对象
  • void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
  • bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

提示：

  • 1 <= word.length <= 25
  • addWord 中的 word 由小写英文字母组成
  • search 中的 word 由 ‘.’ 或小写英文字母组成
  • 最多调用 104 次 addWord 和 search

2.3 解题代码

class TrieNode{
    TrieNode[] next;
    boolean end;
    TrieNode(){
        next = new TrieNode[26];
        end = false;
    }
}

class WordDictionary {
    TrieNode root;
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode now = root;
        for(int i = 0; i < word.length(); ++i){
            int child = word.charAt(i) - 'a';
            if(now.next[child] == null){
                now.next[child] = new TrieNode();
            }
            now = now.next[child];    
        }
        now.end = true;
    }
    
    public boolean search(String word) {
        Queue<TrieNode> q = new LinkedList<>();
        q.offer(root);
        for(int i = 0; i < word.length(); ++i){
            int len = q.size();
            for(int j = 0; j < len; ++j){ 
                TrieNode x = q.peek();
                q.poll();
                if(word.charAt(i) == '.'){
                    for(int k = 0; k < 26; ++k){
                        if(x.next[k] != null){
                            q.offer(x.next[k]);
                        }
                    }
                } else{
                    int child = word.charAt(i) - 'a';
                    if(x.next[child] != null){
                        q.offer(x.next[child]);
                    }
                } 
            }
            if(q.size() == 0){
                return false;
            }
        }
        while(!q.isEmpty()){
            TrieNode x = q.peek();
            if(x.end == true){
                return true;
            }
            q.poll();
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

2.4 解题思路

  1. 套用字典树模板。
  2. 对于搜索，因为癞子的存在，所以需要使用广度优先搜索。

3、单词搜索 II

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

3.3 解题代码

class Solution {
    int[][] dir = {
        {-1, 0},
        {1, 0},
        {0, 1},
        {0, -1},
    };
    Trie trie = new Trie();
    List<String> res = new ArrayList<>();

    public void dfs(TrieNode root, int x, int y, int m, int n, char[][] board, int vis[][], StringBuffer sb){        
        if(root.end == true){
            String str = sb.toString();
            res.add(str);
            root.end = false;
        }
        for(int i = 0; i < 4; ++i){
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if(tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] == 1){
                continue;
            }
            if(root.next[board[tx][ty] - 'a'] != null){
                vis[tx][ty] = 1;
                sb.append(board[tx][ty]);
                dfs(root.next[board[tx][ty] - 'a'], tx, ty, m, n, board, vis, sb);
                sb.deleteCharAt(sb.length() - 1);
                vis[tx][ty] = 0;
            }
        }
    } 

    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;
        int[][] vis = new int[m][n];
        for(int i = 0; i < words.length; ++i){
            trie.insert(words[i]);
        }
        StringBuffer sb = new StringBuffer();
        Queue<Character> q = new LinkedList<>();
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(trie.root.next[board[i][j] - 'a'] != null){
                    vis[i][j] = 1;
                    sb.append(board[i][j]);
                    dfs(trie.root.next[board[i][j] - 'a'], i, j, m, n, board, vis, sb);
                    sb.deleteCharAt(sb.length() - 1);
                    vis[i][j] = 0;
                }             
            }
        }
        return res;
    }
}

class TrieNode{
    TrieNode[] next;
    boolean end;
    TrieNode(){
        next = new TrieNode[26];
        end = false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode now = root;
        for(int i = 0; i < word.length(); ++i){
            int child = word.charAt(i) - 'a';
            if(now.next[child] == null){
                now.next[child] = new TrieNode();
            }
            now = now.next[child];
        }
        now.end = true;
    }
    
    public boolean search(String word) {
        TrieNode now = root;
        for(int i = 0; i < word.length(); ++i){
            int child = word.charAt(i) - 'a';
            if(now.next[child] == null){
                return false;
            }
            now = now.next[child]; 
        }
        return now.end;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode now = root;
        for(int i = 0; i < prefix.length(); ++i){
            int child = prefix.charAt(i) - 'a';
            if(now.next[child] == null){
                return false;
            }
            now = now.next[child]; 
        }
        return true;
    }
}

3.4 解题思路

1, 字典树+回溯思路
2, 如果字典树中存在该字符串，将其放入数组当中，然后将字典树中的该字符串去掉。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/969936.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

快速排序

快速排序

目录 什么是快速排序&#xff1a; 图解&#xff1a; 递归法&#xff1a; 方法一&#xff08;Hoare法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 方法二&#xff08;挖坑法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 非递…
阅读更多...
网络安全尹毅 《网络安全》

网络安全尹毅 《网络安全》

一 网络安全基本概念 1.网络安全定义 安全在字典中的定义是为了防范间谍活动或蓄意破坏、犯罪、攻击而采取的措施。网络安全就是为了防范计算机网络硬件、软件、数据被偶然或蓄意破坏、篡改、窃听、假冒、泄露、非法访问以及保护网络系统持续有效工作的措施总和。网络安全保护…
阅读更多...
6.appender

6.appender

文章目录 一、前言二、源码解析AppenderUnsynchronizedAppenderBaseOutputStreamAppenderConsoleAppenderFileAppenderRollingFileAppenderFileNamePattern 三、总结 一、前言 前一篇文章介绍了appender、conversionRule、root和logger节点的解析, 为的是为本篇详细介绍它们的…
阅读更多...
P9584 「MXOI Round 1」城市

P9584 「MXOI Round 1」城市

题目描述 小 C 是 F 国的总统&#xff0c;尽管这个国家仅存在于网络游戏中&#xff0c;但他确实是这个国家的总统。 F 国由 n 个城市构成&#xff0c;这 n 个城市之间由 n−1 条双向道路互相连接。保证从任意一个城市出发&#xff0c;都能通过这 n−1 条双向道路&#xff0c;…
阅读更多...
什么是Docker多架构容器镜像

什么是Docker多架构容器镜像

什么是Docker多架构容器镜像 在 Docker 中&#xff0c;同一个 Docker 镜像可以在不同的平台上运行&#xff0c;例如在 x86、ARM、PowerPC 等不同的 CPU 架构上。 为了支持这种多平台的镜像构建和管理&#xff0c;Docker 在 17.06 版本时引入了 Manifest 的概念&#xff0c;在…
阅读更多...
Baklib知识中台构建企业智能运营核心架构

Baklib知识中台构建企业智能运营核心架构

内容概要 在数字化转型的浪潮中&#xff0c;企业对于知识的系统化管理需求日益迫切。Baklib作为新一代的知识中台&#xff0c;通过构建智能运营核心架构&#xff0c;为企业提供了一套从知识汇聚到场景化落地的完整解决方案。其核心价值在于将分散的知识资源整合为统一的资产池…
阅读更多...
深度学习机器学习：常用激活函数（activation function）详解

深度学习机器学习：常用激活函数（activation function）详解

目录 Sigmoid Function ReLU&#xff08;Rectified Linear Unit&#xff09; LeakyReLU&#xff08;Leaky Rectified Linear Unit&#xff09; ClippedReLU&#xff08;Clipped Rectified Linear Unit&#xff09; PRelu&#xff08;Parametric ReLU&#xff09; Tanh&am…
阅读更多...
【面试】网络安全常问150道面试题

【面试】网络安全常问150道面试题

1&#xff0c;拿到一个待测网站&#xff0c;你觉得应该先做什么&#xff1f; 信息收集&#xff1a; 服务器相关---&#xff1a;## 系统版本&#xff0c;真实IP&#xff0c;开放端口&#xff0c;使用的中间件 指纹信息---## 有无cdn加速&#xff0c;dns解析记录&#xff0c;是不…
阅读更多...
【Linux】--- 基础开发工具之yum/apt、vim、gcc/g++的使用

【Linux】--- 基础开发工具之yum/apt、vim、gcc/g++的使用

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; Linux网络编程 本篇博客我们来认识一下Linux中的一些基础开发工具 --- yum,vim,gcc/g。 &#x1f3e0; yum &#x1f3b8; 什么是yum 当用户想下载软…
阅读更多...
物联网平台-分布式的设备接入与管理系统

物联网平台-分布式的设备接入与管理系统

乐吾乐物联网平台是由乐吾乐自主研发的一款分布式的设备接入与管理系统&#xff0c;专为满足不断增长的设备接入和数据处理需求而设计。平台集数据采集、分析、监控、告警和通知等功能于一体&#xff0c;并融合了乐吾乐大屏可视化和乐吾乐3D数字孪生技术&#xff0c;帮助用户快…
阅读更多...
Day65_20250213图论part9_dijkstra(堆优化版)|Bellman_ford算法精讲

Day65_20250213图论part9_dijkstra(堆优化版)|Bellman_ford算法精讲

Day65_20250213图论part9_dijkstra(堆优化版)|Bellman_ford算法精讲 dijkstra(堆优化版) 题目 https://www.programmercarl.com/kamacoder/0047.%E5%8F%82%E4%BC%9Adijkstra%E5%A0%86.html 小明参加科学大会 思路 思路 朴素版的dijkstra&#xff0c;时间复杂度为O(n^2)&am…
阅读更多...
动手实现自己的 JVM——Go！（ch01）

动手实现自己的 JVM——Go！（ch01）

动手实现自己的 JVM——Go&#xff01;&#xff08;ch01&#xff09; 参考张秀宏老师的《自己动手写java虚拟机》 为什么需要命令行 在 JMV 中&#xff0c;要运行一个 Java 文件&#xff08;字节码&#xff09;&#xff0c;首先需要找到这个文件。那么&#xff0c;如何找到文件…
阅读更多...
IIS部署netcore程序后，出现500.30错误解决方案之一

IIS部署netcore程序后，出现500.30错误解决方案之一

netcore程序部署到IIS后一直出现错误&#xff0c;访问首页后会跳转到登录页地址&#xff0c;然后看到如下错误 HTTP Error 500.30 - ANCM In-Process Start Failure Common solutions to this issue: The application failed to start The application started but then stopp…
阅读更多...
将Docker容器打包成镜像提交

将Docker容器打包成镜像提交

前言 Docker 是一个开源软件&#xff0c;也是一个开放平台&#xff0c;用于开发应用、交付&#xff08;shipping&#xff09;应用、运行应用。 Docker允许用户将基础设施&#xff08;Infrastructure&#xff09;中的应用单独分割出来&#xff0c;形成更小的颗粒&#xff08;容…
阅读更多...
【设计模式】【行为型模式】命令模式（Command）

【设计模式】【行为型模式】命令模式（Command）

&#x1f44b;hi&#xff0c;我不是一名外包公司的员工&#xff0c;也不会偷吃茶水间的零食&#xff0c;我的梦想是能写高端CRUD &#x1f525; 2025本人正在沉淀中… 博客更新速度 &#x1f44d; 欢迎点赞、收藏、关注&#xff0c;跟上我的更新节奏 &#x1f3b5; 当你的天空突…
阅读更多...
【DDD系列-3】DDD战术设计实践分享

【DDD系列-3】DDD战术设计实践分享

DDD 战术设计概念​ ​ ​​ TMF2 中的概念&#xff1a;​ 领域能力&#xff1a;​ 扩展点&#xff1a;​ DDD 战术设计使用场景​ 复杂业务场景​ 复杂来源面对的需求方更加多样化。​ 1 相同场景不同垂直业务方的需求&#xff08;1688&#xff0c;淘宝&#xff0c;天…
阅读更多...
基于单片机的仓库安防系统（论文+源码）

基于单片机的仓库安防系统（论文+源码）

2.1 需求分析 仓库由于存有大量物品&#xff0c;因此对仓库的监控非常重要&#xff0c;目前仓库已经普遍装有安防系统&#xff0c;以保证仓库的安全&#xff0c;本次基于单片机的仓库安防系统设计&#xff0c;在功能上设计如下&#xff1a; 用户可通过IC卡进入仓库&#xff1…
阅读更多...
使用 AutoMQ 和 Tinybird 分析用户网购行为

使用 AutoMQ 和 Tinybird 分析用户网购行为

前言 在当前竞争激烈的市场环境中&#xff0c;数据分析已成为企业实现差异化和精准营销的关键。通过分析用户行为数据&#xff0c;企业能够深入了解用户的习惯、偏好和行为模式&#xff0c;从而更精准地定位目标市场&#xff0c;制定个性化营销策略&#xff0c;并提供定制化推…
阅读更多...
小米 R3G 路由器刷机教程（Pandavan）

小米 R3G 路由器刷机教程（Pandavan）

小米 R3G 路由器刷机教程&#xff08;Pandavan&#xff09; 一、前言 小米 R3G 路由器以其高性价比和稳定的性能备受用户青睐。然而&#xff0c;原厂固件的功能相对有限&#xff0c;难以满足高级用户的个性化需求。刷机不仅可以解锁路由器的潜能&#xff0c;还能通过第三方固…
阅读更多...
Python数据可视化 - Matplotlib教程

Python数据可视化 - Matplotlib教程

文章目录 前言一、Matplotlib简介及安装1. Matplotlib简介2. 安装Matplotlib 二、Matplotlib Pyplot1. Pyplot介绍2. Pyplot中方法介绍2.1 创建和管理图形2.2 绘制图形2.3 设置图形属性2.4 保存和展示 三、Matplotlib绘图标记1. 介绍2. 基本用法3. 标记大小与颜色4. 标记样式列…
阅读更多...
最新文章

Copyright @ 2022~2023