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

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！