题目：

题目很简单，就是设计command line里的tab键，自由发挥。

设计功能：

(1)返回可能命令集：如果当前字符串是若干个命令字符串的最长共同前缀，返回可能的命令字符串列表；(2)自动补全：如果当前字符串是若干命令字符串的共同前缀，但不是最长共同前缀，则将其补充到最长前缀。eg:dic{document, doctor},输入Tab("d"), 返回"doc";(3)返回最少还需要输入多长的字符才能唯一确定一个单词。

数据结构设计：

由于需要通过前缀的操作，所以选择用Trie。事实上Trie的别称是prefix tree,所有操作prefix的问题都可以考虑使用Trie。插入和查找操作时间复杂度都是O(l),l为平均字符串长度。Trie只有一点比HashTable差，就是Trie不支持delete操作。除了常规的属性外，这里需要在TrieNode类里加上count,用来记录当前节点下有多少个单词,在功能需求(3)里会被用来判断。

分析：

Trie这种数据结构通常都是伴随着DFS搜索的，运气好的话还会要求你Backtrack，比如这道题，这都是套路。另外这道题很容易错，重点是要先明确功能需求。下面分条说明下：(1)需求一规定的是返回当前节点下的所有单词，这里容易漏。比如说，在字典{god, godlike}中，遍历到节点d的时候node.isWord是true,但是后面还有"godlike"这个单词。反应在代码里就是findMatch()函数的判断语句里不要写return.找到一个单词不一定是搜索树的叶子节点，要继续搜索下去。(2)自动补全的要求是补全到最长共同前缀，而不是补全出整个单词。所以判断条件是node.child.size() == 1, 而不是node.count == 1;(3)与自动补全相反，计算最短输入长度是要求目标能补全出整个单词，所以要用node.count来做判断。

总之要先读清楚题，划分好各个函数的边界，然后再开始coding.

code:

import java.util.*;public class TABandTrie {    static class TrieNode{        boolean isWord;        //count: the number of words under this node        int count;        String s;        HashMap
    
      child;        public TrieNode(){            count = 0;            isWord = false;            child = new HashMap
     
      ();        }    }    static class Trie{        TrieNode root;        public Trie(){            root = new TrieNode();        }                public void addWord(String word){            TrieNode node = this.root;            for(int i = 0; i < word.length(); i++){                char c = word.charAt(i);                if(!node.child.containsKey(c)) node.child.put(c, new TrieNode());                node.count++;                node = node.child.get(c);            }            node.isWord = true;            node.s = word;        }    }        public static void findCommon(List
      
        result, TrieNode root, StringBuilder prefix){        //if(root.count > 1 || root.isWord){        //*****如果分叉的数量等于一，注意，这里不能用count判断，上面一行代码会WA        if(root.child.size() > 1 || root.isWord){            result.add(prefix.toString());            return;        }                else{            for(char c : root.child.keySet()){                prefix.append(c);                findCommon(result, root.child.get(c), prefix);            }        }    }        public static void findMatch(List
       
         result, TrieNode root, StringBuilder prefix){        //******寻找到一个单词就放进list,注意，这里不能写return;        if(root.isWord) result.add(prefix.toString());        for(char c : root.child.keySet()){            prefix.append(c);            findMatch(result, root.child.get(c), prefix);            prefix.setLength(prefix.length() - 1);        }    }        public static void tab(List
        
          result, TrieNode root, String s, String prefix){        if(s.length() == 0){            if(root.child.size() == 1) findCommon(result, root, new StringBuilder(prefix));            else findMatch(result, root, new StringBuilder(prefix));            return;        }        char c = s.charAt(0);        prefix += c;        tab(result, root.child.get(c), s.substring(1), prefix);    }        public static int shortest(TrieNode root, String s, int length){    //*******注意，这里只能用count判断，因为要求是需要返回指定的单词，而不是返回最长共    //同前缀。如果是返回最长共同前缀的话用node.child.size() == 1        if(root.count == 1 && !root.isWord || s.length() == 0) return length;        char c = s.charAt(0);        return shortest(root.child.get(c), s.substring(1), length + 1);    }        public static void main(String[] args) {        String[] dictionary = {"abcefegddf","abc","ab","catb","cats","robot","catsa","abcd","cc","document", "doctor"};        // String[] dictionary = {};        Trie trie = new Trie();        for(String s : dictionary){          trie.addWord(s);        }        List
         
           result = new ArrayList
          
           (); tab(result, trie.root,"ca",""); System.out.println(result); System.out.println(shortest(trie.root,"document",0)); }}