【字典树(前缀树) 字符串】2416. 字符串的前缀分数和
本文涉及知识点
字典树(前缀树) 字符串
LeetCode 2416. 字符串的前缀分数和
给你一个长度为 n 的数组 words ,该数组由 非空 字符串组成。
定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。
例如,如果 words = [“a”, “ab”, “abc”, “cab”] ,那么 “ab” 的分数是 2 ,因为 “ab” 是 “ab” 和 “abc” 的一个前缀。
返回一个长度为 n 的数组 answer ,其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。
注意:字符串视作它自身的一个前缀。
示例 1:
输入:words = [“abc”,“ab”,“bc”,“b”]
输出:[5,4,3,2]
解释:对应每个字符串的答案如下:
- “abc” 有 3 个前缀:“a”、“ab” 和 “abc” 。
- 2 个字符串的前缀为 “a” ,2 个字符串的前缀为 “ab” ,1 个字符串的前缀为 “abc” 。
总计 answer[0] = 2 + 2 + 1 = 5 。 - “ab” 有 2 个前缀:“a” 和 “ab” 。
- 2 个字符串的前缀为 “a” ,2 个字符串的前缀为 “ab” 。
总计 answer[1] = 2 + 2 = 4 。 - “bc” 有 2 个前缀:“b” 和 “bc” 。
- 2 个字符串的前缀为 “b” ,1 个字符串的前缀为 “bc” 。
总计 answer[2] = 2 + 1 = 3 。 - “b” 有 1 个前缀:“b”。
- 2 个字符串的前缀为 “b” 。
总计 answer[3] = 2 。
示例 2:
输入:words = [“abcd”]
输出:[4]
解释:
“abcd” 有 4 个前缀 “a”、“ab”、“abc” 和 “abcd”。
每个前缀的分数都是 1 ,总计 answer[0] = 1 + 1 + 1 + 1 = 4 。
提示:
1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 由小写英文字母组成
字典树
字典树各节点记录子树数量。
针对每个word ,一次查询word[0…j] 子孙的数量,累加就可以了。
代码
核心代码
namespace NTmp {template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>class CTrieNode{public:~CTrieNode(){for (auto& [tmp, ptr] : m_dataToChilds) {delete ptr;}}CTrieNode* AddChar(TData ele, int& iMaxID){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifconst int index = ele - cBegin;auto ptr = m_dataToChilds[ele - cBegin];if (!ptr){m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUGm_dataToChilds[index]->m_iID = ++iMaxID;m_childForDebug[ele] = m_dataToChilds[index];
#endif}m_dataToChilds[index]->m_iChildChildCount++;return m_dataToChilds[index];}CTrieNode* GetChild(TData ele){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifreturn m_dataToChilds[ele - cBegin];}protected:
#ifdef _DEBUGint m_iID = -1;std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endifpublic:int m_iLeafIndex = -1;int m_iChildChildCount = 0;protected://CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节//unordered_map<int, CTrieNode*> m_dataToChilds;//时间换空间 大约56字节map<int, CTrieNode*> m_dataToChilds;//时间换空间,空间略优于哈希映射,数量小于256时,时间也优。大约48字节};template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>class CTrie{public:int GetLeadCount(){return m_iLeafCount;}CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par, TData curValue){auto curNode = par->AddChar(curValue, m_iMaxID);FreshLeafIndex(curNode);return curNode;}template<class IT>int Add(IT begin, IT end){auto pNode = &m_root;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin, m_iMaxID);}FreshLeafIndex(pNode);return pNode->m_iLeafIndex;}template<class IT>CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end){auto ptr = &m_root;for (; begin != end; ++begin){ptr = ptr->GetChild(*begin);if (nullptr == ptr){return nullptr;}}return ptr;}CTrieNode<TData, iTypeNum, cBegin> m_root;protected:void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode){if (-1 == pNode->m_iLeafIndex){pNode->m_iLeafIndex = m_iLeafCount++;}}int m_iMaxID = 0;int m_iLeafCount = 0;};}
class Solution {
public:vector<int> sumPrefixScores(vector<string>& words) {NTmp::CTrie<> trie;for (const auto& s: words) {trie.Add(s.begin(), s.end());}vector<int> vRet;for (const auto& s : words) {auto ptr = &trie.m_root;int cnt = 0;for (const auto& ch : s) {ptr = ptr->GetChild(ch);cnt += ptr->m_iChildChildCount;}vRet.emplace_back(cnt);}return vRet;}
};
测试用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<string> words;{Solution slu;words = { "abc", "ab", "bc", "b" };auto res = slu.sumPrefixScores(words);Assert({ 5,4,3,2 }, res);}{Solution slu;words = {"abcd" };auto res = slu.sumPrefixScores(words);Assert({ 4 }, res);}
}

扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【字典树(前缀树) 字符串】2416. 字符串的前缀分数和
本文涉及知识点 字典树(前缀树) 字符串 LeetCode 2416. 字符串的前缀分数和 给你一个长度为 n 的数组 words ,该数组由 非空 字符串组成。 定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。 例如,如果 words [“a”,…...
X-CSV-Reader:一个使用Rust实现CSV命令行读取器
🎈效果演示 ⚡️快速上手 依赖导入: cargo add csv读取实现: use std::error::Error; use std::fs::File; use std::path::Path;fn read_csv<P: AsRef<Path>>(filename: P) -> Result<(), Box<dyn Error>> {le…...
集成ECharts到若依框架:原理与使用方法详解
ECharts 是一个强大的开源数据可视化库,基于 JavaScript,能够创建丰富多彩的图表和交互数据展示。结合若依框架(RuoYi),我们可以非常方便地将 ECharts 集成到系统中,实现数据的可视化展示。本文将详细介绍 …...
【机器学习】——线性模型
💻博主现有专栏: C51单片机(STC89C516),c语言,c,离散数学,算法设计与分析,数据结构,Python,Java基础,MySQL,linux…...
最全的Redis常用命令
Redis是一个开源的内存数据结构存储系统,用作数据库、缓存和消息代理。它支持多种类型的数据结构,如字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)…...
sourcetree推送到git上面
官网:Sourcetree | Free Git GUI for Mac and Windows 下载到1次提交 下载后打开 点击跳过 下一步 名字邮箱 点击clone 把自己要上传的代码粘贴到里面去 返回点击远程->点击暂存所有 加载完毕后,输入提交内容提交 提交完成了 2次提交 把文件夹内的…...
勒索病毒的策略与建议
随着网络技术的快速发展,勒索病毒攻击成为全球范围内日益严重的网络安全威胁。勒索病毒通过加密用户文件或锁定系统来勒索赎金,给个人和企业带来了巨大的损失。因此,了解如何应对勒索病毒攻击至关重要。本文将概述一些有效的防范措施和应对策…...
doxygen 1.11.0 使用详解(十四)——输出格式
目录 HTMLLATEXMan pagesRTFXMLDocBookCompiled HTML Help (a.k.a. Windows 98 help)Qt Compressed Help (.qch)Eclipse HelpXCode DocSetsPostScriptPDF The following output formats are directly supported by doxygen: HTML Generated if GENERATE_HTML is set to YES i…...
java list<AnalystEducationDO> 转成List<AnalystEducationRespVO>两个对象的属性一样
如果AnalystEducationDO和AnalystEducationRespVO两个类的属性完全相同,且遵循Java Bean的命名规范(即具有相应的getter和setter方法),你可以利用一些库来简化转换过程,比如Apache BeanUtils或Spring Framework的BeanU…...
[Algorihm][简单多状态DP问题][买卖股票的最佳时机含冷冻期][买卖股票的最佳时机含手续费]详细讲解
目录 1.买卖股票的最佳时机含冷冻期1.题目链接买卖股票的最佳时机含冷冻期2.算法原理详解3.代码实现 2.买卖股票的最佳时机含手续费1.题目链接2.算法原理详解3.代码实现 1.买卖股票的最佳时机含冷冻期 1.题目链接 买卖股票的最佳时机含冷冻期 2.算法原理详解 思路ÿ…...
微服务:利用RestTemplate实现远程调用
打算系统学习一下微服务知识,从今天开始记录。 远程调用 调用order接口,查询。 由于实现还未封装用户信息,所以为null。 下面我们来使用远程调用用户服务的接口,然后封装一下用户信息返回即可。 流程图 配置类中注入RestTe…...
【Linux】TCP的三次握手和四次挥手
三次握手 在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握手建立一个连接。注意!三次握手只是用来建立连接用的,和TCP可靠稳定没有关系,TCP的可靠是通过重传和检错等机制实现的。 默认创建一个socket后ÿ…...
爬山算法全解析:掌握优化技巧,攀登技术高峰!
一、引言 爬山算法是一种局部搜索算法,它基于当前解的邻域中进行搜索,通过比较当前解与邻域解的优劣来更新当前解,从而逐步逼近最优解。本文将对爬山算法进行详细的介绍。 二、爬山算法简介 爬山算法是一种基于贪心策略的优化算法ÿ…...
使用 Ollama框架 下载和使用 Llama3 AI大模型的完整指南
🏡作者主页:点击! 🤖AI大模型部署与应用专栏:点击! ⏰️创作时间:2024年5月24日20点59分 🀄️文章质量:96分 目录 💥Ollama介绍 主要特点 主要优点 应…...
最新流媒体在线音乐系统网站源码| 音乐社区 | 多语言 | 开心版
最新流媒体在线音乐系统网站源码 源码免费下载地址抄笔记 (chaobiji.cn)...
中国改革报是什么级别的报刊?在哪些领域具有较高的影响力?
中国改革报是什么级别的报刊?在哪些领域具有较高的影响力? 《中国改革报》是国家发展和改革委员会主管的全国性综合类报纸。它在经济领域和改革发展方面具有重要的影响力,是传递国家政策、反映改革动态的重要平台。该报对于推动中国的经济改…...
乡村振兴的乡村公共服务提升:提升乡村公共服务水平,满足农民多样化需求,构建幸福美好的美丽乡村
目录 一、引言 二、乡村公共服务提升的必要性 (一)满足农民多样化需求 (二)促进乡村经济发展 (三)构建幸福美好的美丽乡村 三、乡村公共服务面临的挑战 (一)基础设施薄弱 &a…...
【在 Windows 上使用 ADB 安装 Android 设备上的 atx-agent】
在进行 Android 应用的 UI 自动化测试时,通常需要在设备上安装一些辅助工具。其中一个常用的工具是 atx-agent,它可以帮助我们在 Android 设备上进行 UI 自动化操作。本文将介绍如何在 Windows 环境下使用 ADB 安装 Android 设备上的 atx-agent。 1. 下…...
iptables 防火墙
linux防火墙基础 iptables的表,链结构 数据包控制的匹配流程 编写防火墙规则 基本语法,控制类型 添加,查看,删除规则 规则的匹配条件 iptables组件 netfilter :属于内核态的功能体系,是一个内核模块…...
软件设计师笔记1
分享一下学习软考时做的笔记,笔者太懒了,后续篇章都没咋记录,现在放出来水几篇文章 另外,本章内容都是结合教材,B站课堂记录。下一篇软考笔记知识点来自真题 软考笔记 第一章 1. 计算机的组成 1. 控制器 控制器由…...
如何快速解决Windows依赖问题:终极系统优化指南
如何快速解决Windows依赖问题:终极系统优化指南 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 你是否曾经遇到过打开心爱的游戏时突然弹出"缺少…...
ComfyUI-VideoHelperSuite视频工作流完整指南:从图像序列到专业视频的5个关键步骤
ComfyUI-VideoHelperSuite视频工作流完整指南:从图像序列到专业视频的5个关键步骤 【免费下载链接】ComfyUI-VideoHelperSuite Nodes related to video workflows 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-VideoHelperSuite ComfyUI-VideoHelpe…...
FlashMLA:把 KV Cache 压缩到原来的八分之一
标准 MHA 的 KV Cache 是推理显存的第一大户。LLaMA-7B,32 层,每层 32 头,HeadDim128,SeqLen128K——KV Cache 吃 40GB。MLA(Multi-head Latent Attention)用低秩分解把 KV 映射到一个远小于 HeadDim 的潜在…...
JMeter接口测试进阶:从功能验证到生产级性能工程
1. 这不是“点点点就能跑通”的接口测试,而是你真正能扛住压测的底气很多人第一次打开 JMeter,以为它只是个“图形化 Postman”——填 URL、选方法、点执行,看到绿色 Success 就觉得“接口测完了”。我带过三届测试团队,几乎每届都…...
【趋势检测和隔离】使用小波进行趋势检测和隔离研究附Matlab代码
✅作者简介:热爱科研的Matlab仿真开发者,擅长毕业设计辅导、数学建模、数据处理、程序设计科研仿真。🍎完整代码获取 定制创新 论文复现点击:Matlab科研工作室👇 关注我领取海量matlab电子书和数学建模资料 dz…...
Axure RP中文语言包终极指南:快速实现界面本地化
Axure RP中文语言包终极指南:快速实现界面本地化 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包。支持 Axure 11、10、9。不定期更新。 项目地址: https://gitcode.com/gh_mirrors/ax/axure-cn 还在为Axure RP复杂…...
CFD湍流模型不确定性量化:特征空间扰动框架原理与应用
1. 项目概述与核心挑战在计算流体力学(CFD)的工程实践中,我们常常面临一个核心困境:如何高效且可靠地预测复杂湍流?雷诺平均纳维-斯托克斯(RANS)模型因其在计算成本和工程实用性之间的绝佳平衡&…...
AppImageLauncher:Linux桌面应用的3分钟智能管家
AppImageLauncher:Linux桌面应用的3分钟智能管家 【免费下载链接】AppImageLauncher Helper application for Linux distributions serving as a kind of "entry point" for running and integrating AppImages 项目地址: https://gitcode.com/gh_mirro…...
Windows电脑安装安卓应用:告别模拟器的轻量级解决方案
Windows电脑安装安卓应用:告别模拟器的轻量级解决方案 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 你是否曾经渴望在Windows电脑上运行安卓应用…...
微信小程序数据可视化:5步实现ECharts专业级图表集成方案
微信小程序数据可视化:5步实现ECharts专业级图表集成方案 【免费下载链接】echarts-for-weixin 基于 Apache ECharts 的微信小程序图表库 项目地址: https://gitcode.com/gh_mirrors/ec/echarts-for-weixin 面对微信小程序中复杂数据可视化需求的挑战&#x…...
