如何比較anagrams而不使用toCharArray方法？

/* 
* 
* 
*/ 

import java.util.Scanner; 
import java.util.Arrays; 


public class Anagram 
{ 
    public static void main(String[] args) 
    { 

Scanner sc = new Scanner(System.in); 
String one, two; 

System.out.print("Enter first sentence: "); 
String s1 = sc.nextLine(); 
System.out.print("Enter second sentence: "); 
String s2 = sc.nextLine(); 

sc.close(); 

s1 = s1.toLowerCase(); 
char[] chars = s1.toCharArray(); 
Arrays.sort(chars); 
String sort1 = new String(chars); 
System.out.println(sort1 + " are the letters of " + s1 + " in order"); 

s2 = s2.toLowerCase(); 
char[] chars2 = s2.toCharArray(); 
Arrays.sort(chars2); 
String sort2 = new String(chars2); 
System.out.println(sort2 + " are the letters of " + s2 + " in order"); 

if(sort1.equals(sort2)) 
    System.out.println(s1 + " is an anagram of " + s2); 


    } 
}

這是我的程序，使用toCharArray比較anagrams，但是是否可以做到每個'a'到'z'並將它追加到排序列表而不是toCharArray？如何比較anagrams而不使用toCharArray方法？

來源

2011-08-25 Ron_ish

因此，爲了澄清，您正在尋找一種方法來比較字符串中的字母字符（即忽略數字，標點符號等）？ –

是隻比較正確的字母字符。 –

我還注意到，當我測試我的程序與重播和歐芹它的作品，甚至聽和沉默的話，但是當我嘗試使用莎士比亞比較尋求一個短語，它將排序字母，但沒有將它們定義爲anagrams –

我會考慮使用Pattern和Matcher類來找到"[a-zA-Z]"中的字符的正則表達式。然後你可以循環結果

String string = "abcd123"; 
Pattern pattern = Pattern.compile("[a-zA-Z]"); 
Matcher matcher = pattern.matcher(string); 
while (matcher.find()) { 
    System.out.println(matcher.group()); 
}

來源

2011-08-25 01:31:44 krock

當我在while替換此代碼（matcher.find（））我得到一個類型爲 –

那麼有幾個選項。如果你想要做的就是避免調用「toCharArray」，那麼你可以循環字符串和字符的方式創建，但我懷疑這是你在找什麼？

你也可以做一個實現如下（僞代碼）：

public void areAnagrams(String s1, String s2) 
{ 
    int[] aNumLetters = new int[26]; 

    s1.toLowerCase(); 
    s2.toLowerCase(); 

    for each char c in s1 
    aNumLetters[(int)c - ((int)'a')]++; 

    for each char c in s2 
    aNumLetters[(int)c - ((int)'a')]--; 

    for each int nLetterCount in aNumLetters 
    if nLetterCount != 0 
     return false 

    return true; 
}

來源

2011-08-25 01:38:32 harbinja

的錯誤非法啓動，如果我不想返回false或true並將其附加到排序列表中，但是我已經使用Array.sort並且不知道如何在沒有Array.sort的情況下追加它方法 –

@Ron_ish我不確定我明白你的意思。你想追加到排序列表中的什麼？你指的是什麼排序清單？你是說你需要對信件進行分類嗎？ – harbinja

如果我在小寫句子中找到每個'a'，並輸入它並將其附加到已排序的字符串中，則例如使用我的輸出上方的方法將輸入PARSLEY和REPLAY這兩個字 - aelprsy是按順序排序的字母並比較對第二個將是aelprsy的是香芹的字母順序，最後比較兩個排序，如果他們相等，因此，他們是anagrams –

如果你通過了「一」，那麼「B」等等，那麼基本上你」字符串做一個天真搜索我會執行一個冒泡排序，它的性能會比使用快速排序的Arrays.sort()差。

我會想象toCharArray()轉換具有微不足道的一次性成本，所以試圖微觀優化，這將是徒勞無益的。

取而代之的是，考慮到兩個字符串是字謎，它們的排序字母是否相等並不重要，只是它們必須包含每個字母的相同數量。也就是說，如果一個字符串包含3 A和1 B和2 N，那麼它就是BANANA的一個字謎。

以此爲武裝，我們可以想象，通過迭代第一個字符串中的每個字符並構建<Character, Integer>計數的Map，可以比較兩個字符串是否是字謎。然後迭代第二個字符串並對每個字符進行反向遞減計數。

掃描第二個字符串後，您只需檢查所有計數是否爲零。這種方法的一個優點是，當掃描第二個字符串時，只要字符數量低於零，就可以將檢查「短路」 - 這意味着第二個字符串比第一個字符串具有更多的字符，因此它們不是字謎。

上面概述了一個最佳情況O(n)算法（基本上，每個字符串只有一個通過），假設地圖操作的最佳情況爲O(1)。在最糟糕的情況下，我認爲我們正在尋找O(n^2)。

將此對比於quicksort，它具有相同的最差情況下的性能，但最好是O(n log(n))。

當然，在實踐中，對於較短的字符串，快速排列字符數組可能會更快。然而，隨着字符串變得更長，上述基於地圖的算法應該開始被證明更有效率，尤其是，與短路。

來源

2011-08-25 02:31:51

我同意toCharArray節省了大量的時間，而不是但是由於它是作業並且具有特定的工作，所以這是迄今爲止所需的方式。我會嘗試你的方式，因爲我一直在嘗試所有其他的選擇，但我只是想知道如何通過一個字母詞來做到這一點。此外，在決定它們是否爲字符之前，我們的輸出顯示兩個單詞的排序字母列表也非常重要 –

您可以使用單個String.replaceAll()從字符串中刪除所有非字母字符，然後其餘代碼應該是正確的。

這是因爲String.replaceAll()使用正則表達式。請查看javadocs for Pattern以獲取Java中正則表達式的快速參考。要特別注意Character Classes部分;從示例中，您應該能夠構建與「非字母字符」匹配的模式。在String.replaceAll()中使用該模式作爲第一個參數，使用空字符串作爲第二個參數。

它不是性能方面最有效的實現，但可能是最簡單的代碼。

來源

2011-08-25 03:56:02

如何比較anagrams而不使用toCharArray方法？

回答

相關問題