网站做标签,网页内容编辑,婚介网站模板,网站开发专业优势本文涉及知识点
字典树#xff08;前缀树) 字符串
LeetCode 2416. 字符串的前缀分数和
给你一个长度为 n 的数组 words #xff0c;该数组由 非空 字符串组成。 定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。 例如#xff0c;如果 words [“a”,…本文涉及知识点
字典树前缀树) 字符串
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 {templateclass TData char, int iTypeNum 26, TData cBegin aclass 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_mapTData, CTrieNode* m_childForDebug;
#endifpublic:int m_iLeafIndex -1;int m_iChildChildCount 0;protected://CTrieNode* m_dataToChilds[iTypeNum] { nullptr };//空间换时间 大约216字节//unordered_mapint, CTrieNode* m_dataToChilds;//时间换空间 大约56字节mapint, CTrieNode* m_dataToChilds;//时间换空间,空间略优于哈希映射数量小于256时时间也优。大约48字节};templateclass TData char, int iTypeNum 26, TData cBegin aclass CTrie{public:int GetLeadCount(){return m_iLeafCount;}CTrieNodeTData, iTypeNum, cBegin* AddA(CTrieNodeTData, iTypeNum, cBegin* par, TData curValue){auto curNode par-AddChar(curValue, m_iMaxID);FreshLeafIndex(curNode);return curNode;}templateclass ITint 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;}templateclass ITCTrieNodeTData, 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;}CTrieNodeTData, iTypeNum, cBegin m_root;protected:void FreshLeafIndex(CTrieNodeTData, iTypeNum, cBegin* pNode){if (-1 pNode-m_iLeafIndex){pNode-m_iLeafIndex m_iLeafCount;}}int m_iMaxID 0;int m_iLeafCount 0;};}
class Solution {
public:vectorint sumPrefixScores(vectorstring words) {NTmp::CTrie trie;for (const auto s: words) {trie.Add(s.begin(), s.end());}vectorint 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;}
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorstring 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
