eindeutiges Wort Abkürzung alternative Lösungen?

Question

Hilfe! Zahlreiche Lösungen löste es in HashMap, es effizienter als Arraylist, aber der Einfachheit halber von Code und als Anfänger-Coder ist:

1. Ich frage mich, ob es in Arraylist gelöst werden können: alle Elemente abkürzen erste und die gegebene Wort, dann vergleichen, ob abgekürztes gegebenes Wort mit irgendeinem der Elemente in dem Array übereinstimmt. Bitte prüfen Sie den Code, der mit "why not ..." beginnt und die Funktion "isUnique2". Es gibt immer Fehler, jemand sagt mir bitte, wie es behoben werden kann.

2. Mein zweiter Gedanke war: erste & & letzte Element & & Länge zu vergleichen. Wäre das nicht viel einfacher? Wenn nicht, sag mir bitte, warum es falsch ist.

   //<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

In Bezug auf Ihre erste Frage: Die Idee könnte in Ordnung angesehen werden (aber meine Leistung Kommentaren unten sehen), aber Sie scheinen zu sein inkonsequent, wenn Sie die abkürzen wollen Wörterbuch Artikel: versuchen Sie es in den Konstruktor zu tun, und dann wieder in isUnique2() Sie tun: String n_w = abbreviate(dictionary[i]);

in Bezug auf Ihre zweite Frage: ich kno w Sie wissen bereits die Antwort. :-)
Warum weiß ich das? Im Konstruktor UniqueWordAbbr() prüfen Sie bereits auf Kollisionen Ihrer Abkürzungen: if (!map.containsKey(abbr)). Sie wissen also schon, dass Kollisionen passieren und berücksichtigt werden müssen. Die erste Verteidigungslinie gegen Kollisionen ist gutes Hashing (= eine gute Abkürzungsmethode) - d. H. Eine Methode, die Kollisionen äußerst unwahrscheinlich macht. Ihre in abbreviate() ausgedrückte Idee ist nicht gut zum Erzeugen einzigartiger Hashes. Also muss Ihr Programm oft zu den nächsten Verteidigungslinien zurückkehren, die Sie codieren müssen (und so wird Ihr Programm die Ausführung dieses zusätzlichen Codes verlangsamen ...)
Aus der Sicht der Leistung würde ich empfehlen Folgendes ist zu beachten:
1. es ist Zeitverschwendung, einen wichtigen Teil des Wörterbuchs bei jedem Anruf bei isUnique2() immer wieder abzukürzen.
Es ist sinnvoller, das gesamte Wörterbuch weniger häufig zu kürzen, aber das macht im Konstruktor zukünftige Aktualisierungen des vorhandenen Wörterbuchs unmöglich. Leistungsmäßig ist es am besten, bei jedem Update zu kürzen.
2. Sie müssen auch nicht abgekürzte und abgekürzte Formulare zusammen speichern, was Sie nur lokal in List abbr_dictionary tun, die vorübergehend in isUnique2() existiert. So verlieren Sie es schnell ...
3. Sie suchen Ihr Wörterbuch mit linearer Suche. Dies ist ineffizient, da die Komplexität dieser Suche O (n) ist. Aber unter Verwendung von z.B. Die binäre Suche würde erfordern, dass die Wörterbuch-Hashes (Ihre "Abkürzungen") nach jedem Update geordnet bleiben.