java - 独特的单词缩写替代解决方案？

Question

救命啊!许多解决方案在 HashMap 中解决了这个问题，它比 ArrayList 更高效，但是为了代码简单和作为初学者:

1. 我想知道是否可以在 ArrayList 中解决:首先缩写所有元素和给定单词，然后比较缩写的给定单词是否与数组中的任何元素匹配。请检查以“why not...”开头的代码和函数“isUnique2”。它总是报错，请有人告诉我如何修复它。

2. 我的第二个想法是:比较第一个 && 最后一个元素 && 长度。这不是简单得多吗？如果不是，请告诉我为什么错了。

   //<first letter><number><last letter> check if a word is unique
   //Given dictionary = [ "deer", "door", "cake", "card" ] ，isUnique("dear") -> false， isUnique("cart") -> true， isUnique("cane") -> false， isUnique("make") -> true
   
   public class UniqueWordAbbr {
   
   Map<String, String> map= new HashMap<String, String>();
   
   public static void main(String[] args){
       String[] dictionary  = { "deer", "door", "cake", "card" };
       UniqueWordAbbr uwa = new UniqueWordAbbr(dictionary);
       System.out.println(uwa.isUnique2 (dictionary,"cane"));
       System.out.println(uwa.isUnique("word"));
   }
   //why not create array to check if elements match???
   public boolean isUnique2(String[] dictionary, String word) {
       String abbr_w = abbreviate(word);
       List abbr_dictionary = new ArrayList(); 
   
       for(int i = 0; i<dictionary.length; i++){
           String n_w = abbreviate(dictionary[i]);
           abbr_dictionary.add(n_w);
       }
       for (Object copy : abbr_dictionary) {
           if (abbr_w.equals(copy))
                return false;
            else return true;
       }
       return false;
   }
   //1. abbreviate 
   private String abbreviate(String str){
       return str.charAt(0)+ Integer.toString(str.length()-2) + str.charAt(str.length()-1);
   }   
   //2. establish the map, convert array into map
   public UniqueWordAbbr(String[] dictionary){
         for(int i = 0; i < dictionary.length; i++){
           String abbr = abbreviate(dictionary[i]);
           //always check if map does NOT contain first!
           if (!map.containsKey(abbr)){
               map.put(abbr, dictionary[i]);
           }else{
               map.put(abbr, "");
           }   
       }
   }
   // check if word is unique
   public boolean isUnique(String word) {
       String abbr_w = abbreviate(word);
       //为啥不直接 查询 map.containsKey(abbr_w)?
           if (map.containsKey(abbr_w)) {
               //why also need to compare the value? 
               if (map.get(abbr_w).equals(word)){
                   return true;
               }else {
                   return false;
               }
           }
       return true;
   }
   

   }

Answer 1

关于你的第一个问题:这个想法可能被认为是好的(但请参阅下面我的性能评论)，但当你想要缩写字典项目时，你似乎不一致:你尝试这样做它在构造函数中，然后再次在 isUnique2() 中执行: String n_w = abbreviate(dictionary[i]);

关于你的第二个问题:我知道你已经知道答案了。 :-)
我为什么知道这个？在构造函数中UniqueWordAbbr()您已经检查了缩写的冲突:if (!map.containsKey(abbr)) 。所以您已经知道，碰撞会发生并且必须加以考虑。防止冲突的第一道防线是良好的散列(=良好的缩写方法)——即一种使冲突极不可能发生的方法。您的想法在 abbreviate() 中表达不擅长生成唯一的哈希值。因此，您的程序将不得不经常恢复到您必须编码的下一道防线(因此您的程序将减慢执行这些附加代码的速度......)

从性能的角度来看我建议您考虑:
1. 每次调用isUnique2()时一次又一次地缩写字典的重要部分是浪费时间。 .
减少对整个字典的缩写更为合理，但在构造函数中这样做会禁用对现有字典的 future 更新。从性能角度来看，通常最好在每次更新时进行缩写。
2. 您还必须将未缩写形式和缩写形式存储在一起，现在只能在 List abbr_dictionary 中本地执行此操作。暂时存在于 isUnique2() 。所以你很快就会失去它...
3. 您正在使用线性搜索来搜索字典。这是低效的，因为该搜索的复杂度是 O(n)。但使用例如二分搜索需要在每次更新后保持字典哈希(您的“缩写”)的顺序。