words abbreviation

题目：
在一个字典里有一堆英文单词，现在要把这些单词缩写成（前缀 + 字符串长度 + 尾字母）的形式，而且现在有两个限制条件：
(1)要求缩写后的字符串可以唯一表示原单词；
(2)有相同长度的单词在缩写后放在一起。

分析：
(1)trie树的大多数功能可以用HashTable来替代，但是prefix功能是HashTable不好做到的。由于最终的缩写需要考虑前缀，所以选择trie这种数据结构；
(2)要满足第一个限制条件，只能靠前缀来区分有相同长度和尾字母的原单词。所以需要在trie的数据结构里加一个变量count,表示当前节点子节点的个数。所以当count为一的时候，说明这个前缀是唯一区别于其他单词的；
(3)为了满足第二个限制条件，所以把限制条件转换成字符加在每个单词的前面，这样在建树的时候就自动把满足条件的同一类单词放到一个分支里了。比如这道题的另一个变形：有相同尾字母的放在一起，就是把尾字母加到头部建树。由于是使用字典树，所以每个节点的key是字符型的变量。这里有一个易错的地方，就是不要把字符串长度直接放在头部，以为长度等于2的单词会和长度等于20的单词会被分到同一个分支里。我的做法是用(char)(' ' + word.lengt())来代替长度。这个做法适用单词长度小于128的情况，一般情况下是可以满足的。

code:

import java.util.*;public class WordsAbbreviation {    static class TrieNode{        int count;        boolean isWord;        HashMap child;        public TrieNode(){            count = 0;            child = new HashMap();        }    }    static class Trie{        TrieNode root;        public Trie(){            root = new TrieNode();        }        void addWord(String Word){            TrieNode root = this.root;            for(int i = 0; i  result1 = new ArrayList();        List result2 = new ArrayList();        Trie trie1 = buildSameTailTree(dictionary);        Trie trie2 = buildSameLengthTree(dictionary);        for(String word : dictionary){            TrieNode root1 = trie1.root.child.get(word.charAt(word.length() - 1));            result1.add(compress(word, root1, ""));            TrieNode root2 = trie2.root.child.get((char)(' ' + word.length()));            result2.add(compress(word, root2, ""));        }        System.out.println(result1);        System.out.println(result2);    }}

关键字：trie

版权声明

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