上一篇给大家推荐了《推荐7款好用的终端工具 》,本篇给大家分享一个Java Map使用多个映射案例。
问题描述
许多单词和另外一些单词相似，例如，通过改变第一个字母，单词wine可以变成，dine fine line mine nine pine vine 改变第3个字母，wide wife wipe wire…….
他们仅仅通过改变一个字母，可以得到很多个单词，假设有一个词典，89000个单词，将单词长度相同，且只有一个字母不同的单词放到一组。
思路
使用一个MAP对象，其中key是单词，value是用一个字母替换能从key变换得到的一系列单词。
主要问题是如何从包含89000个单词的数组中构造MAP对象。
方法一：暴力解决
先判断除一个字母不同外，两个单词是否相等。代码如下：
private static Boolean oneCharOff(String word1,String word2){
if(word1.length()!=word2.length()) return false;
int diffs = 0;
for(int i=0;i<word1.length();i++){
if(word1.charAt(i)!=word2.charAt(i))
if(++diffs>1)
return false;
}
return true;
}
计算一个MAP对象，该对象以一些单词作为关键字而以只在一个字母处不同的一列单词作为关键字的值，该函数对一个89000单词的词典运行96秒。
public static Map<String, List<String>> computeAdjacentWord(List<String> theWords){
//单词映射，单词作为关键字，而只有一个单词和该单词不同的一系列单词作为值。
Map<String, List<String>> adjWords = new TreeMap<String, List<String>>();
String[] words = new String[theWords.size()];
theWords.toArray(words);
for(int i=0;i<words.length;i++){
for(int j = i+1;j<words.length;j++){
if(oneCharOff(words[i], words[j])){
update(adjWords,words[i], words[j]);
update(adjWords,words[j], words[i]);
}
}
}
return adjWords;
}
private static <KeyType> void update(Map<KeyType, List<String>> adjWords, KeyType string, String string2) {
List<String> lst = adjWords.get(string);
if(lst == null){
lst = new ArrayList<String>();
adjWords.put(string, lst);
}
lst.add(string2);
}该算法的问题在于速度慢，一个明显的改进就是避免比较不同长度的单词。可以把单词按照长度分组，然后对各分组进行上述程序。
方法二：避免比较单词长度
可以把单词按照长度分组，然后对各分组进行上述程序。为此可以使用第二个映射，此时关键字是整数，代表单词长度，而值是该长度对应的单词集合。
public static Map<String, List<String>> computeAdjacentWord(List<String> theWords){
String[] words = new String[list.size()]; list.toArray(words); for(int i=0;i<words.length;i++){ for(int j = i+1;j<words.length;j++){ if(oneCharOff(words[i], words[j])){ update(adjWords,words[i], words[j]); update(adjWords,words[j], words[i]); } } } } return adjWords; }
Map<String, List<String>> adjWords = new TreeMap<String, List<String>>();
Map<Integer, List<String>> wordsByLength = new TreeMap<Integer, List<String>>();
for(String w:theWords){
//根据长度对单词分组
update(wordsByLength,w.length(),w);
}
for(List<String> list:wordsByLength.values()){引入第二个集合后，可以使words.length的值成倍减少，也就可以使双重循环的次数减少，从而缩短运行时间。
与第一个方法比较，第二个方法只是在边际上编程困难，其运行时间为51秒，大约快了一倍。
方法二中的update方法和oneCharOff方法参考方法一。
方法三：
另外有附加了一些映射，先和方法二一样，将单词按长度分组，然后分别对每组运算。
假设对长度为4的单词操作，这是首先要找出像wine和nine这样的单词，他们除第一个外单词完全相同，对于这种单词，可以删除第一个字母，留下3个单词做代表，这样就形成一个Map，其中关键字为这个代表，而其值是所有包含同一代表的单词的一个List。
每一个Map中的list对象都形成单词的一个集团，其中任何一个单词均可以通过单个字母替换变成另一个单词，因此在这个最后的Map构成之后，很容易遍历它以及添加一些项到正在计算的原始Map中。
然后我们使用一个新的Map再处理4个字母单词组的第二个字母。此后第三个字母，最后是第四个字母。
public static Map<String, List<String>> computeAdjacentWord(List<String> theWords){
Map<String, List<String>> adjWords = new TreeMap<String, List<String>>();
Map<Integer, List<String>> wordsByLength = new TreeMap<Integer, List<String>>();
for(String w:theWords){
//根据长度对单词分组
update(wordsByLength,w.length(),w);
}
//每一组单词按去掉一个字母后是否相同再次分组映射
for(Map.Entry<Integer, List<String>> entry : wordsByLength.entrySet()){
List<String> groupsWords = entry.getValue();
int groupNum = entry.getKey();
//从第一个字母开始，依次处理每个字母，映射到Map中。
for(int i=0;i<groupNum;i++){
Map<String, List<String>> repToWord = new TreeMap<String, List<String>>();
//从第一个字母开始，依次处理每个字母，映射到Map中。
for(String str:groupsWords){
String rep = str.substring(0,i) + str.substring(i+1);
update(repToWord, rep, str);
}
//放到最终的Map映射中。
for(List<String> wordClique : repToWord.values()){
if(wordClique.size()>2)
for(String s1 : wordClique)
for(String s2 : wordClique)
if(s1 != s2)
update(adjWords, s1, s2);
}
}
}
return adjWords;
}private static <KeyType> void update(Map<KeyType, List<String>> adjWords, KeyType string, String string2) { List<String> lst = adjWords.get(string); if(lst == null){ lst = new ArrayList<String>(); adjWords.put(string, lst); } lst.add(string2); }该算法对89000个单词处理改进到了4秒，大大提升了效率。
