TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4191
  • 题目
  • P4191中山纪念中学 Trie
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    字母(Trie)树是一个表示一个字符串集合中所有字符串的前缀的数据结构,其有如下特征:

    1.树的每一条边表示字母表中的一个字母 
    2.树根表示一个空的前缀 
    3.树上所有其他的节点都表示一个非空前缀,每一个节点表示的前缀为树根到该节点的路径上所有字母依次连接而成的字符串。 
    4.一个节点的所有出边(节点到儿子节点的边)中不存在重复的字母。 
         
    现在Matej手上有N个英文小写字母组成的单词,他想知道,如果将这N个单词中的字母分别进行重新排列,形成的字母树的节点数最少是多少。

    输入格式

    第一行包含一个正整数N(1<=N<=16) 
    接下来N行每行一个单词,每个单词都由小写字母组成。 
    单词的总长度不超过1,000,000。

    输出格式

    输出仅一个正整数表示N个单词经过重新排列后,字母树的最少节点数。

    样例输入

    10
    jgda
    dbfdjj
    hehegdfh
    faeejic
    acagdgfcjc
    jifiigdbif
    fdbdii
    ch
    c
    adccdd

    样例输出

    42


    来源  感谢1879570236