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

【字典树(前缀树) 字符串】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. 字符串的前缀分数和

本文涉及知识点 字典树&#xff08;前缀树) 字符串 LeetCode 2416. 字符串的前缀分数和 给你一个长度为 n 的数组 words &#xff0c;该数组由 非空 字符串组成。 定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。 例如&#xff0c;如果 words [“a”,…...

X-CSV-Reader:一个使用Rust实现CSV命令行读取器

&#x1f388;效果演示 ⚡️快速上手 依赖导入&#xff1a; cargo add csv读取实现&#xff1a; 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 是一个强大的开源数据可视化库&#xff0c;基于 JavaScript&#xff0c;能够创建丰富多彩的图表和交互数据展示。结合若依框架&#xff08;RuoYi&#xff09;&#xff0c;我们可以非常方便地将 ECharts 集成到系统中&#xff0c;实现数据的可视化展示。本文将详细介绍 …...

【机器学习】——线性模型

&#x1f4bb;博主现有专栏&#xff1a; C51单片机&#xff08;STC89C516&#xff09;&#xff0c;c语言&#xff0c;c&#xff0c;离散数学&#xff0c;算法设计与分析&#xff0c;数据结构&#xff0c;Python&#xff0c;Java基础&#xff0c;MySQL&#xff0c;linux&#xf…...

最全的Redis常用命令

Redis是一个开源的内存数据结构存储系统&#xff0c;用作数据库、缓存和消息代理。它支持多种类型的数据结构&#xff0c;如字符串&#xff08;strings&#xff09;、哈希&#xff08;hashes&#xff09;、列表&#xff08;lists&#xff09;、集合&#xff08;sets&#xff09…...

sourcetree推送到git上面

官网&#xff1a;Sourcetree | Free Git GUI for Mac and Windows 下载到1次提交 下载后打开 点击跳过 下一步 名字邮箱 点击clone 把自己要上传的代码粘贴到里面去 返回点击远程->点击暂存所有 加载完毕后&#xff0c;输入提交内容提交 提交完成了 2次提交 把文件夹内的…...

勒索病毒的策略与建议

随着网络技术的快速发展&#xff0c;勒索病毒攻击成为全球范围内日益严重的网络安全威胁。勒索病毒通过加密用户文件或锁定系统来勒索赎金&#xff0c;给个人和企业带来了巨大的损失。因此&#xff0c;了解如何应对勒索病毒攻击至关重要。本文将概述一些有效的防范措施和应对策…...

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两个类的属性完全相同&#xff0c;且遵循Java Bean的命名规范&#xff08;即具有相应的getter和setter方法&#xff09;&#xff0c;你可以利用一些库来简化转换过程&#xff0c;比如Apache BeanUtils或Spring Framework的BeanU…...

[Algorihm][简单多状态DP问题][买卖股票的最佳时机含冷冻期][买卖股票的最佳时机含手续费]详细讲解

目录 1.买卖股票的最佳时机含冷冻期1.题目链接买卖股票的最佳时机含冷冻期2.算法原理详解3.代码实现 2.买卖股票的最佳时机含手续费1.题目链接2.算法原理详解3.代码实现 1.买卖股票的最佳时机含冷冻期 1.题目链接 买卖股票的最佳时机含冷冻期 2.算法原理详解 思路&#xff…...

微服务:利用RestTemplate实现远程调用

打算系统学习一下微服务知识&#xff0c;从今天开始记录。 远程调用 调用order接口&#xff0c;查询。 由于实现还未封装用户信息&#xff0c;所以为null。 下面我们来使用远程调用用户服务的接口&#xff0c;然后封装一下用户信息返回即可。 流程图 配置类中注入RestTe…...

【Linux】TCP的三次握手和四次挥手

三次握手 在TCP/IP协议中&#xff0c;TCP协议提供可靠的连接服务&#xff0c;采用三次握手建立一个连接。注意&#xff01;三次握手只是用来建立连接用的&#xff0c;和TCP可靠稳定没有关系&#xff0c;TCP的可靠是通过重传和检错等机制实现的。 默认创建一个socket后&#xff…...

爬山算法全解析:掌握优化技巧,攀登技术高峰!

一、引言 爬山算法是一种局部搜索算法&#xff0c;它基于当前解的邻域中进行搜索&#xff0c;通过比较当前解与邻域解的优劣来更新当前解&#xff0c;从而逐步逼近最优解。本文将对爬山算法进行详细的介绍。 二、爬山算法简介 爬山算法是一种基于贪心策略的优化算法&#xff…...

使用 Ollama框架 下载和使用 Llama3 AI大模型的完整指南

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;AI大模型部署与应用专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年5月24日20点59分 &#x1f004;️文章质量&#xff1a;96分 目录 &#x1f4a5;Ollama介绍 主要特点 主要优点 应…...

最新流媒体在线音乐系统网站源码| 音乐社区 | 多语言 | 开心版

最新流媒体在线音乐系统网站源码 源码免费下载地址抄笔记 (chaobiji.cn)...

中国改革报是什么级别的报刊?在哪些领域具有较高的影响力?

中国改革报是什么级别的报刊&#xff1f;在哪些领域具有较高的影响力&#xff1f; 《中国改革报》是国家发展和改革委员会主管的全国性综合类报纸。它在经济领域和改革发展方面具有重要的影响力&#xff0c;是传递国家政策、反映改革动态的重要平台。该报对于推动中国的经济改…...

乡村振兴的乡村公共服务提升:提升乡村公共服务水平,满足农民多样化需求,构建幸福美好的美丽乡村

目录 一、引言 二、乡村公共服务提升的必要性 &#xff08;一&#xff09;满足农民多样化需求 &#xff08;二&#xff09;促进乡村经济发展 &#xff08;三&#xff09;构建幸福美好的美丽乡村 三、乡村公共服务面临的挑战 &#xff08;一&#xff09;基础设施薄弱 &a…...

【在 Windows 上使用 ADB 安装 Android 设备上的 atx-agent】

在进行 Android 应用的 UI 自动化测试时&#xff0c;通常需要在设备上安装一些辅助工具。其中一个常用的工具是 atx-agent&#xff0c;它可以帮助我们在 Android 设备上进行 UI 自动化操作。本文将介绍如何在 Windows 环境下使用 ADB 安装 Android 设备上的 atx-agent。 1. 下…...

iptables 防火墙

linux防火墙基础 iptables的表&#xff0c;链结构 数据包控制的匹配流程 编写防火墙规则 基本语法&#xff0c;控制类型 添加&#xff0c;查看&#xff0c;删除规则 规则的匹配条件 iptables组件 netfilter &#xff1a;属于内核态的功能体系&#xff0c;是一个内核模块…...

软件设计师笔记1

分享一下学习软考时做的笔记&#xff0c;笔者太懒了&#xff0c;后续篇章都没咋记录&#xff0c;现在放出来水几篇文章 另外&#xff0c;本章内容都是结合教材&#xff0c;B站课堂记录。下一篇软考笔记知识点来自真题 软考笔记 第一章 1. 计算机的组成 1. 控制器 控制器由…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...