2010-08-23 103 views
5

我的問題是,我有2個字符串,說String1 & String2。現在我想檢查這兩個字符串是否包含相同的字符,而不管它們的順序如何。如何比較包含相同字符的2個字符串

假設String1= "qwerty"String2= "qywter"。現在這些字符串包含相同的字符,但順序不同。那麼是否有任何函數可以用來表明這些字符串包含相同的字符?可以equals()方法做到這一點?

所有幫助表示讚賞。

+6

應的結果是在什麼情況下,他們有相同的字符,但不相同的字符數? (如「qwerty」和「qywtery」?)它們包含相同的字符,但不包含相同數量的字符。 – MikeTheReader 2010-08-23 18:29:26

回答

17
char[] chars1 = string1.toCharArray(); 
char[] chars2 = string2.toCharArray(); 
Arrays.sort(chars1); 
Arrays.sort(chars2); 

return Arrays.equals(chars1, chars2); 
+1

但他們返回什麼? – prasad 2010-08-23 18:36:17

+0

@prasad - 我不明白你的評論 – Bozho 2010-08-23 18:37:48

+0

我的意思是,做「返回Arrays.equals(chars1,chars2);」聲明 返回一個布爾值或一個int? – prasad 2010-08-23 18:39:26

2

您可以使用String.equals,儘管是間接的。首先,你需要一個輔助方法:

// given a String, sorts its chars and return it as another String 
public static String sorted(String s) { 
    char[] arr = s.toCharArray(); 
    Arrays.sort(arr); 
    return new String(arr); 
} 

然後,你可以有:

String s1 = "qwerty"; 
    String s2 = "qywter"; 

    System.out.println(sorted(s1)); // eqrtwy 

    System.out.println(sorted(s1).equals(sorted(s2))); // true 

注意,這不是最有效的算法 - 這是O(N log N)時間,並利用多餘的空間 - 但應該工作罰款的短弦。對於長字符串,您希望手動通過每個char(或Unicode代碼點)(而不是toCharArray()),並且可能使用線性時間counting sort

如果你不關心具體的字符數匹配(例如"xxxyyy""xy"具有相同的字符,儘管在不同的數字),那麼你可以使用一組類似的表示(java.util.BitSet)。

// given a string, returns its used char set as a java.util.BitSet 
public static BitSet usedChar(String s) { 
    BitSet bs = new BitSet(); 
    for (int i = 0; i < s.length(); i++) { 
     bs.set(s.charAt(i)); 
    } 
    return bs; 
} 

然後,你可以有:

System.out.println(
     usedChar("xxxyyy").equals(usedChar("xy")) 
    ); // true 

    System.out.println(
     usedChar("xyz").equals(usedChar("abc")) 
    ); // false 
2

這取決於你是否真的想要的字符或你真的想碼點,然後它的事項是否要算重複與否。這裏有一個解決方案:

public class a { 
    public static void main(String[] args) { 
    String s1 = "qwerty"; 
    String s2= "qywter"; 
    System.out.println(codePointSet(s1).equals(codePointSet(s2))); 
    } 
    public static Set<Integer> codePointSet(String s) { 
    Set<Integer> set = new TreeSet<Integer>(); 
    for (int i = 0, cp; i < s.length(); i += Character.charCount(i)) { 
     cp = s.codePointAt(i); 
     set.add(cp); 
    } 
    return set; 
    } 
} 
0

String.equals()將不適用於您的特定情況。您可能需要編寫自己的方法來以這種方式來對字符串進行等同處理。

1
int[] f = new int[(int)char.MaxValue]; 
foreach (var c in string1) f[(int)c]++; 
foreach (var c in string2) f[(int)c]--; 
return f.Max() == 0 && f.Min() == 0; 

當string1.length()>> char.MaxValue和它具有較低的大O符號複雜度時,這是更好的解決方案。

編輯這實際上是C#代碼,但您可以很容易地在Java中實現類似的結果。

+0

有趣的方法,但肯定不是Java。 – 2010-08-23 18:33:13

0

如果您有需要比較長的字符串,你並不需要成功的保證,你可以做這樣的事情:

  1. 確保字符串的長度相同
  2. 爲每個圖像
  3. 加起來所有字符(鑄成整數)
  4. 加起來字符的平方(再次鑄成整數)
  5. 比較平方和和資金
  6. 如果它們相同,則字符串包含相同的字符。

其實我花了一些時間試圖弄清楚哪裏不行,但我想不出一個。我的直覺告訴我,我在這裏錯過了一些東西,或者這是一個很好的比較器。

0

兩個步驟需要

  1. 做兩個字符串的異或,如果XOR爲0,那麼你肯定部分。

  2. 如果xor爲0,則找到兩個字符串的ascii值的總和,如果ascii總和相同,則 這兩個字符串都是相同的。

希望這有助於