字典树判断是否为前缀编码

水深无声 2023-07-06 06:19 13阅读 0赞

前缀编码：如果一个编码不是另一个编码的前缀，则为前缀编码。

给定几个字符串，判断是否是前缀编码。  
直接字符串匹配。

模板

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 100005
      
    int ch[maxn][15];
    int val[maxn];
    int sz;
    char str[20];
    int num[maxn];
    int t;
    int len;
      
    bool setup(char*s)
    { 
        bool ok=true;
        int u=0,n=strlen(s);
        for(int i=0; i<n; i++)
        { 
            int id=s[i]-'0';
            if(ch[u][id]==0)
            { 
                ch[u][id]=++sz;
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
            }
            u=ch[u][id];
            if(val[u]>0)
            { 
                ok=false;
                break;
            }
        }
        val[u]++;
        if(ok)
        { 
            for(int i=0; i<=9; i++)
                if(ch[u][i]!=0)
                { 
                    ok=false;
                    break;
                }
        }
        return ok;
    }
      
    int main()
    { 
        scanf("%d",&t);
        int cas=1;
        while(t--)
        { 
            bool ok=true;
            scanf("%d",&len);
            memset(ch,0,sizeof(ch));
            sz=0;
            for(int i=1; i<=len; i++)
            { 
                scanf("%s",str);
      
                if(ok)
                    ok=setup(str);
            }
            printf("Case #%d: ",cas);
            if(ok)
                printf("Yes\n");
            else
                printf("No\n");
            cas++;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关前缀树(字典树/Trie) -----Java实现

目录一.前缀树 1.什么是前缀树 2.前缀树的举例二.前缀树的实现 1.前缀树的数据结构 1.插入字符串 2.查找字符串 3.查找前缀三.词典中最长的

╰半橙微兮°/ 2024年03月25日 20:32/ 0 赞/ 140 阅读

相关【数据结构】前缀树/字典树

目录 1.概述 2.代码实现 3.应用 > 本文参考： > LeetCode [208.实现 Trie (前缀树)][208._ Trie]

雨点打透心脏的1/2处/ 2023年10月07日 22:38/ 0 赞/ 76 阅读

相关 Trie ——前缀树、字典树

说在前面： > `Map`映射数据结构和`Trie`的异同： > 相同：都能够根据`key`进行映射得到对应的值。 > 不同： > ① `Trie`中查询/添

逃离我推掉我的手/ 2023年07月10日 13:00/ 0 赞/ 69 阅读

相关字典树判断是否为前缀编码

前缀编码：如果一个编码不是另一个编码的前缀，则为前缀编码。给定几个字符串，判断是否是前缀编码。直接字符串匹配。模板 include<bits/stdc+

水深无声/ 2023年07月06日 06:19/ 0 赞/ 14 阅读

相关 leetcode 208. 实现 Trie (前缀树)-字典树

字典树 [百度百科][Link 1] 大概是一个26叉树插入每次插入的时候如果当前没有这个分支就新建节点查找每次查找都从根节点开始，随着单词的前后顺

谁践踏了优雅/ 2023年02月27日 10:33/ 0 赞/ 26 阅读

相关 python 判断字符串是否为空,字典是否为空,列表是否为空,元组是否为空的方法

在python 中 None,空列表\[\],空元组(),空字典\{\},0都是被程序判断为False ,所以我们判断对象是否为空可以直接是用if x 或者if not x 的

我会带着你远行/ 2023年01月19日 14:58/ 0 赞/ 338 阅读

相关判断是否为完全二叉树

解题思路完全二叉树看起来就是一个“满二叉树右下角缺了一块” 需要引入一个标志位来区分两个阶段针对一个完全二叉树，进行层序遍历，会出现两种阶段 1）任何一个节点

梦里梦外;/ 2023年01月11日 09:23/ 0 赞/ 190 阅读

相关 Immediate Decodability(字典树-判断是否存在前缀)

Immediate Decodability Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/

蔚落/ 2022年08月04日 13:41/ 0 赞/ 177 阅读

相关数据结构——Trie 字典树前缀树

一、什么是Trie Trie不同于二分搜索树、堆、线段树等二叉树结构，Trie是一个多叉树。使用场景：通讯录高效搜索，专为处理字符串设计的。比如字典中有n条数据

清疚/ 2022年05月14日 15:27/ 0 赞/ 350 阅读

相关 208.实现一个字典树（前缀树）

//实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 // // 示例: // Trie trie =

╰半夏微凉°/ 2021年06月22日 15:38/ 0 赞/ 503 阅读