poj 2001 Shortest Prefixes (trie树)

2016年8月16日 0 作者 CrazyKK

poj 2001 题目链接

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

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

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

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