poj 2001 Shortest Prefixes (trie树)

poj 2001 题目链接

题意:给出n个字符串的表,问每个字符串的简化表示。简化表示的要求是,以该字符串的最短的而且不能产生歧义的前缀来表示。

思路:字典树,多一个cnt属性,每次insert的时候,路过的每个节点的cnt++

find的时候从root往下扫。。遇到的cnt为1的节点结尾的字符串。。就是该单词的唯一表示。。。

按照这个思路写了一发。。。1A好开心哈哈哈

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz