2個字的字謎

Question

我正在練習java和一些算法，所以我想創建一個程序來查看2個單詞是否是對方的字謎。我的方法是使用快速排序對單詞進行排序，然後查看它們是否匹配。我測試了我quicksort功能，它似乎工作。也許我的謎語功能是錯誤的？我測試了我的代碼對"tac"和"cat"，我得到false。

有人可以看看我的代碼，看看我出錯了嗎？

我的代碼：

public static boolean anagram(String s, String t) { 
    int lenS = s.length(); 
    int lenT = t.length(); 
    if (lenS != lenT) { 
     return false; 
    } 
    else if (quicksort(s) == quicksort(t)) { 
      return true; 
    } 
    else { return false;} 
} 

public static String quicksort(String s) { 
    int len = s.length(); 
    int median = len/2;  //pivot point 
    String sortedString; 
    if (len < 2) { 
     return s; 
    } 
    else { 
     String str = s.replace(String.valueOf(s.charAt(median-1)), ""); 
     char pivot = s.charAt(median-1); 
     String less = ""; 
     String greater = ""; 
     for (int i = 0; i < str.length(); i++) { 
      char pointed = str.charAt(i); 
      if (pointed <= pivot) { 
       less += String.valueOf(pointed); 
      } 
      else { 
       greater += String.valueOf(pointed); 
      } 
     } 
     sortedString = quicksort(less) + pivot + quicksort(greater); 
     return sortedString; 
    } 
} 

Answer 1

quicksort(s) == quicksort(t)

裏面就你的問題 - 你與==比較字符串，不.equals()！你不應該使用==比較字符串，拋開愚蠢的學術例子。這是錯誤和不可預知的行爲的主流。有時它會工作，但大部分時間它不會（見here有關該主題的更深層次的解釋，但在實踐中的字符串規則只是「始終使用equals()，從不使用==。）

所以考慮到在你的if語句的條件應該是quicksort(s).equals(quicksort(t))。

順便說一句，你可以繞過整個quicksort()方法，只是使用Arrays.sort()，而不是（對字符串進行調用toCharArray()後）。一般它總是更好地使用圖書館排序，而不是寫你自己的排序方法，但我知道有家庭作業和類似的地方這是必需的！

Answer 2

我一直在想使用quicksort來解決字謎，並認爲我有一個捷徑。如果我們同時處理兩個單詞，我們可以在每次迭代中比較數據透視指數。在一天結束時，我們儘量避免完成2個快速排序。採用這種方法，我們使用樞軸索引作爲完成結果的預覽。

例如在迭代1中，快排1的樞軸索引最終位於位置4，其值爲「a」並且快排2的樞轉索引最終位於位置6並且值「c」我們不能使用捷徑（還）。然而，例如在迭代1中，快排1的樞轉索引結束於位置4，其值爲「c」，快排2的樞轉索引最終位於位置6，其值爲「a」那麼我們可以確定它們不會是字謎。

我們可以在每次迭代的比較過程中繼續使用這種方法。

這應該會將比較的效率從「2n log（n）」更改爲「n log（n）/ 2」（400％性能提升）。