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

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()时一次又一次地缩写字典的重要部分是浪费时间。
减少缩写整个字典的频率更合理，但在构造函数中这样做会禁用对现有字典的未来更新。在性能方面，通常最好在每次更新时缩写。
2.您还必须将未缩写和缩写的形式存储在一起，您现在只能在isUnique2()中临时存在的List abbr_dictionary本地进行。所以你赶紧把它弄丢...
3.您正在使用线性搜索搜索字典。这是低效的，因为此搜索的复杂性为 O(n(。但是使用例如二叉搜索需要在每次更新后保持字典哈希(您的"缩写"(的顺序。