Design CML-TAB
题目：
题目很简单，就是设计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 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)); }}关键字：trie
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！