当前位置: 首页 > news >正文

【数据结构-字典树】力扣14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”

示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。

提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空,则仅由小写英文字母组成

class Solution {
private:struct dt { vector<dt*> children;bool isEnd;dt() : children(26, nullptr), isEnd(false) {}};dt* root;
public:Solution() {root = new dt();  // 初始化根节点}string longestCommonPrefix(vector<string>& strs) {for(string word : strs){if(word.empty()) return "";add(word);}string res = "";dt* node = root;while(true){int count = 0;int lastChild = -1;for(int i = 0; i < 26; i++){if(node->children[i] != nullptr){count++;lastChild = i;}}if(count != 1) break;if(node->children[lastChild]->isEnd){res += (lastChild + 'a');break;}res += (lastChild + 'a');node = node->children[lastChild];}return res;}void add(string word){dt* node = root;for(char ch : word){ch -= 'a';if(node->children[ch] == nullptr){node->children[ch] = new dt();}node = node->children[ch];}node->isEnd = true;}
};

我们可以使用tried树来解决这道题,首先先将所有strs的word构造出一个字典树。接下来我们从字典树的根节点不断向下查找,我们看他有几个子节点,如果有多个子节点,就说明不需要继续添加字符了,因为只有当children的数量为1个的时候,说明是公共前缀。

然后我们还要检查我们选择的下一个节点是不是某个word的结尾,如果是的话,就将其添加到res后,停止继续查找添加。

相关文章:

【数据结构-字典树】力扣14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀&#xff0c;返回空字符串 “”。 示例 1&#xff1a; 输入&#xff1a;strs [“flower”,“flow”,“flight”] 输出&#xff1a;“fl” 示例 2&#xff1a; 输入&#xff1a;strs [“dog”,“racecar…...

《深入浅出HTTPS​​​​​​​​​​​​​​​​​》读书笔记(31):HTTPS和TLS/SSL

《深入浅出HTTPS​​​​​​​​​​》读书笔记&#xff08;31&#xff09;&#xff1a;HTTPS和TLS/SSL TLS/SSL协议和应用层协议无关&#xff0c;它只是加密应用层协议&#xff08;比如HTTP&#xff09;并传递给下层的TCP。 HTTP和TLS/SSL协议组合在一起就是HTTPS, HTTPS等…...

Go学习:Go语言中if、switch、for语句与其他编程语言中相应语句的格式区别

Go语言中的流程控制语句逻辑结构与其他编程语言类似&#xff0c;格式有些不同。Go语言的流程控制中&#xff0c;包括if、switch、for、range、goto等语句&#xff0c;没有while循环。 目录 1. if 语句 2. switch语句 3. for语句 4. range语句 5. goto语句&#xff08;不常用…...

L30.【LeetCode笔记】设计链表

1.题目 707. 设计链表 - 力扣&#xff08;LeetCode&#xff09; 你可以选择使用单链表或者双链表&#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性&#xff1a;val 和 next 。val 是当前节点的值&#xff0c;next 是指向下一个节点的指针/引用。 如果是双向…...

java日志框架详解-Log4j2

一、概述 Apache Log4j 2 &#xff08;Log4j – Apache Log4j 2&#xff09;是对Log4j的升级&#xff0c;它比其前身Log4j 1.x提供了重大改进&#xff0c;并参考了Logback中优秀的设计&#xff0c;同时修复了Logback架构中的一些问题。被誉为是目前最优秀的Java日志框架&#x…...

C++中vector追加vector

在C中&#xff0c;如果你想将一个vector追加到另一个vector的后面&#xff0c;可以使用std::vector的成员函数insert或者std::copy&#xff0c;或者简单地使用std::vector的push_back方法逐个元素添加。这里我将展示几种常用的方法&#xff1a; 方法1&#xff1a;使用insert方…...

加一(66)

66. 加一 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a; class Solution { public:vector<int> plusOne(vector<int>& digits) {bool plus_one true;for (int i digits.size() - 1; i > 0; --i) {if (plus_one) {int tmp digits[i] 1;if …...

远程连接-简化登录

vscode通过ssh连接远程服务器免密登录&#xff08;图文&#xff09;_vscode ssh-CSDN博客...

canvas的基本用法

canvas canvas元素简介 1.是个container元素<canvas width100 height100></canvas>&#xff0c;有开闭标签 2.有且只有width和height两个attribute&#xff0c;不需要写单位 canvas的基本使用 const canvasEl document.getElementById(canvas01) const ctx …...

Tailwind CSS - Tailwind CSS 引入(安装、初始化、配置、引入、构建、使用 Tailwind CSS)

一、Tailwind CSS 概述 Tailwind CSS 是一个功能优先的 CSS 框架&#xff0c;它提供了大量的实用类&#xff08;utility classes&#xff09;&#xff0c;允许开发者通过组合这些类来快速构建用户界面 Tailwind CSS 与传统的 CSS 框架不同&#xff08;例如&#xff0c;Bootstr…...

鸿蒙开发黑科技“stack叠层”替代customdialog

前一篇提到的问题,本篇博文提出了一个解决方案: arkui-x LongPressGesture触发customdialog踩坑记录-CSDN博客 前一段时间遇到的这个问题,通过排除法观察,锁定为customdialog组件有bug,极为容易挂死。不论如何调整使用方法,都还是会触发挂死。 反馈给arkui团队,说是在…...

FreeRTOS从入门到精通 第十五章(事件标志组)

参考教程&#xff1a;【正点原子】手把手教你学FreeRTOS实时系统_哔哩哔哩_bilibili 一、事件标志组简介 1、概述 &#xff08;1&#xff09;事件标志位是一个“位”&#xff0c;用来表示事件是否发生。 &#xff08;2&#xff09;事件标志组是一组事件标志位的集合&#x…...

智慧园区管理平台实现智能整合提升企业运营模式与管理效率

内容概要 在当今数字化的背景下&#xff0c;智慧园区管理平台正逐渐成为企业提升运营效率和管理模式的重要工具。这个平台汇聚了多种先进技术&#xff0c;旨在通过智能整合各类资源与信息&#xff0c;帮助企业实现全面的管理创新。 智慧园区管理平台不仅仅是一个数据处理工具…...

markdown公式特殊字符

个人学习笔记 根号 在 Markdown 中&#xff0c;要表示根号 3&#xff0c;可以使用 LaTeX 语法来实现。常见的有以下两种方式&#xff1a; 行内公式形式&#xff1a;使用一对美元符号 $ 将内容包裹起来&#xff0c;即 $\sqrt{3}$ &#xff0c;在支持 LaTeX 语法渲染的 Markdow…...

【深度分析】微软全球裁员计划不影响印度地区,将继续增加当地就业机会

当微软的裁员刀锋掠过全球办公室时&#xff0c;班加罗尔的键盘声却愈发密集——这场资本迁徙背后&#xff0c;藏着数字殖民时代最锋利的生存法则。 表面是跨国公司的区域战略调整&#xff0c;实则是全球人才市场的地壳运动。微软一边在硅谷裁撤年薪20万美金的高级工程师&#x…...

学习数据结构(5)单向链表的实现

&#xff08;1&#xff09;头部插入 &#xff08;2&#xff09;尾部删除 &#xff08;3&#xff09;头部删除 &#xff08;4&#xff09;查找 &#xff08;5&#xff09;在指定位置之前插入节点 &#xff08;6&#xff09;在指定位置之后插入节点 &#xff08;7&#xff09;删除…...

刷题记录 HOT100回溯算法-5:22. 括号生成

题目&#xff1a;22. 括号生成 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()",…...

Keepalived高可用集群企业应用实例二

一、实现ipvs的高可用性 ipvs相关配置 虚拟服务器配置结构&#xff1a; virtual_server ip port { …… real_server { …… } real_server { …… } } virtual server (虚拟服务器)的定义格式 virtual_server ip port 定义虚拟主机ip地址及其端口 virtual_server …...

C++计算特定随机操作后序列元素乘积的期望

有一个长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​。初始序列的所有元素均为 0 0 0。再给定正整数 m m m、 c c c和 ( n − m 1 ) (n-m1) (n−m1)个正整数 b 1 , b 2 , . . . , b n − m 1 b_1,b_2,...,b_{n-m1} b1​,b2​,...,bn−m1​…...

c++字母大小写转换

可以通过标准库中的 <algorithm> 和 <cctype> 头文件来实现大小写转换。以下是常用的方法&#xff1a; 1. 使用 std::transform 和 std::toupper/std::tolower 1.1 转换为大写 #include <iostream> #include <string> #include <algorithm> //…...

LoRA训练助手GPU显存优化:Qwen3-32B INT4量化后仅需9.2GB显存稳定运行

LoRA训练助手GPU显存优化&#xff1a;Qwen3-32B INT4量化后仅需9.2GB显存稳定运行 1. 引言&#xff1a;当大模型遇见显存焦虑 如果你尝试过在个人电脑上运行大语言模型&#xff0c;大概率会遇到一个令人头疼的问题&#xff1a;显存不足。特别是像Qwen3-32B这样拥有320亿参数的…...

别再只盯着芯片手册了!用CC6902SO搭建电流检测电路,这些实测数据和避坑经验更重要

别再只盯着芯片手册了&#xff01;用CC6902SO搭建电流检测电路&#xff0c;这些实测数据和避坑经验更重要 第一次用CC6902SO搭建电流检测电路时&#xff0c;我完全按照芯片手册推荐的电路设计&#xff0c;结果发现实际输出和理论值差了将近15%。这让我意识到&#xff0c;真正影…...

基于python的民宿预定管理系统设计与实现j470j

目录同行可拿货,招校园代理 ,本人源头供货商功能需求分析用户端功能房东端功能管理员端功能技术实现要点扩展功能建议项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作同行可拿货,招校园代理 ,本人源头供货商 功能需求分析 民宿…...

解锁欧空局10米土地利用数据:从注册到实战应用全流程解析

1. 欧空局10米土地利用数据简介 第一次接触欧空局WorldCover平台的朋友可能会被这个10米分辨率的土地利用数据惊艳到。作为一个长期和遥感数据打交道的从业者&#xff0c;我可以很负责任地说&#xff0c;这个数据集在精度和实用性上确实很能打。简单来说&#xff0c;它把全球地…...

BilibiliDown:让B站视频下载变得简单高效

BilibiliDown&#xff1a;让B站视频下载变得简单高效 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors/bi/BilibiliDo…...

Qwen3-TTS开源模型教程:Gradio接口封装+API服务发布完整指南

Qwen3-TTS开源模型教程&#xff1a;Gradio接口封装API服务发布完整指南 1. 前言&#xff1a;为什么你需要一个专属的语音合成服务&#xff1f; 想象一下&#xff0c;你正在开发一个智能客服应用&#xff0c;需要为不同国家的用户提供多语言的语音回复&#xff1b;或者你是一个…...

环境管理从未如此简单:Miniconda-Python3.9镜像快速入门指南

环境管理从未如此简单&#xff1a;Miniconda-Python3.9镜像快速入门指南 1. 为什么选择Miniconda-Python3.9镜像 Python作为当今最流行的编程语言之一&#xff0c;在数据科学、机器学习和Web开发等领域有着广泛应用。但Python环境管理一直是开发者面临的痛点之一&#xff0c;…...

Phi-4-mini-reasoning:轻量级推理模型在人工智能浪潮中的定位

Phi-4-mini-reasoning&#xff1a;轻量级推理模型在人工智能浪潮中的定位 1. 轻量级推理模型的时代价值 当ChatGPT等千亿参数大模型占据媒体头条时&#xff0c;一个容易被忽视的趋势正在悄然兴起——轻量级推理模型正在特定领域展现出惊人的实用性。Phi-4-mini-reasoning正是…...

英雄联盟智能助手:如何在选人阶段获得不公平优势?终极指南揭秘本地化工具LeagueAkari

英雄联盟智能助手&#xff1a;如何在选人阶段获得不公平优势&#xff1f;终极指南揭秘本地化工具LeagueAkari 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League…...

Polars 2.0大规模清洗崩溃全解析:内存溢出、Schema冲突、LazyFrame中断——3类高频致命报错的5分钟修复方案

第一章&#xff1a;Polars 2.0大规模清洗崩溃全解析&#xff1a;内存溢出、Schema冲突、LazyFrame中断——3类高频致命报错的5分钟修复方案 当处理TB级结构化数据时&#xff0c;Polars 2.0的LazyFrame虽带来性能飞跃&#xff0c;却也因底层执行引擎变更放大了三类典型崩溃风险。…...