Q:给定一个字符串数组，每个字符串都会有一个最短前缀，这个最短前缀能够唯一的确定这个字符串，返回由这些最短前缀组成的字符串数组。
A:其实，只要找到重复的最长前缀就可以了。例如字符串abc,abcd,abcdef，bcd,bcde,bcdef，重复的最长前缀为就只有abcd,bcde。
代码如下

import java.util.*;
public class 字典树最短前缀
{
    public static Node buildTree(String[] arr)
    {
        Node root=new Node();
        Node root_temp=root;
        for (String str :arr )
        {
            for (int i=0;i<str.length() ;i++ )
            {
                char temp=str.charAt(i);
                boolean find=false;
                for (Node child:root_temp.children )
                {
                    if (child.c==temp)
                    {
                        find=true;
                        child.count++;
                        root_temp=child;
                        break;
                    }
                }
                if (!find)
                {
                    Node add_temp=new Node(temp,1);
                    root_temp.children.add(add_temp);
                    root_temp=add_temp;
                }
            }
            root_temp=root;
        }
        return root;
    }
    public static String[] search(String[] arr,Node root)
    {
        Node root_temp=root;
        String[] res=new String[arr.length];
        int index=0;
        for (String str:arr )
        {
            StringBuilder sb=new StringBuilder();
            boolean not_all_match=false;
            for (int i=0;i<str.length() ;i++ )
            {
                Node res_temp=find(str.charAt(i),root_temp);
                if (res_temp!=null&&res_temp.count>1)
                {
                    sb.append(str.charAt(i)+"");
                    root_temp=res_temp;
                }
                else
                {
                    sb.append(str.charAt(i)+"");
                    res[index++]=sb.toString();
                    not_all_match=true;
                    break;
                }
            }
            if (!not_all_match)
                res[index++]=sb.toString();
            sb=new StringBuilder();
            root_temp=root;
        }
        return res;
    }
    public static Node find(char c,Node root)
    {
        for (Node child:root.children )
        {
            if (child.c==c)
            {
                return child;
            }
        }
        return null;
    }
    public static void main(String[] args) 
    {
        String[] arr={"abc","abcd","abcdefg","bcd","bcdefg"};
        Node root=buildTree(arr);
        String[] res=search(arr,root);
        for (String str:res )
        {
            System.out.println(str);
        }
    }
}
class Node
{
    public char c;
    public int count;
    public List<Node> children=new ArrayList<>();
    public Node(){}
    public Node(char c,int count)
    {
        this.c=c;
        this.count=count;
    }
}

这个题目中不能在每次用字符串与字典树对比时，都把相应节点的计数都减一，比如abc,abcd,abcdef的字典树，在取最后一个abcdef时，所有节点的计数都为1，这样就把之前的信息覆盖掉了，无法判断abcdef怎么取。
如果上来就是按字典树的套路一通乱做，会发现做不出来，原因还是没有了解到这个题目的本质。再仔细分析一下题目，abc，abcd对应的最短前缀都是自身，因为它们都重复过，只有abcdef没有全部重复，所以只要找到最长的重复的字符串就可以了。
所以解决问题的本质还是在于先分析问题，洞悉问题的关键所在，至于使用什么数据结构，什么算法都只是实现你的分析的工具。如果本末倒置，自然绕来绕去，还是解不了题。
想起之前美团笔试的一道题，颇有异曲同工之妙。之前还鄙视这种题目，觉得没什么技术含量，没有什么华丽的操作，现在看来还是自己naive了，因为分析问题是关键，数据结构与算法只是工具。
这里贴上链接：http://blog.csdn.net/yf_li123/article/details/77828633
如果一上来就是出栈入栈的各种操作，肯定就又是GG了。