給定兩個字符串，是一個接一個

Question

的字謎我剛開始通過「破譯編碼訪談」持續和有此問題的以下解決方案：

public static bool isAnagram(String s, String t) 
{ 
    if (s == "" || t == "") return false; 
    else if (s.Length != t.Length) return false; 

    int[] letters = new int[256]; 
    char[] s_array = s.ToCharArray(); 

    foreach(char c in s_array) 
    { 
     letters[c]++; 
    } 

    for (int i = 0; i < t.Length; i++) 
    { 
     int c = t[i]; 
     if (--letters[c] < 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

這是非常從逐字解決方案只能在C＃中使用，而不能使用Java，並且需要一些額外的空檢查。我也使用LINQ解決了這個問題，但想要一個不涉及排序的解決方案。

這種方法可以變得更優雅嗎？代碼工作得很好，我只想知道是否有更優雅或更好的解決方案。謝謝！！

Answer 1

此代碼應爲你工作：

public static bool IsAnagram(string s1, string s2) 
{ 
    if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) 
     return false; 
    if (s1.Length != s2.Length) 
     return false; 

    foreach (char c in s2) 
    { 
     int ix = s1.IndexOf(c); 
     if (ix >= 0) 
      s1 = s1.Remove(ix, 1); 
     else 
      return false; 
    } 

    return string.IsNullOrEmpty(s1); 
} 

編輯：添加非LINQ版本。

您還可以添加一些額外的空值和空值檢查，並將解決方案移動到StringBuilder以提高性能，但代碼的意圖是明確的。

Answer 2

可以兩個字符串進行排序和比較

Answer 3

排序，然後比較順序的工作原理：

bool isAnagram = "asdf".OrderBy(c => c).SequenceEqual("fdsa".OrderBy(c => c)); 

或者，你可以使用一個Dictionary<char, int>跟蹤字符計數（Unicode的字符超過256可能的值）。另外，在迭代字符串的字符之前，您不需要調用ToArray()。

Answer 4

這個非LINQ解決方案如何？

public static bool IsAnagram(String s, String t) 
{ 
    if ((s == null) || (t == null) || (s.Length == 0) || (t.Length == 0) || (s.Length != t.Length)) 
     return false; 

    var ta = t.ToCharArray(); 

    foreach (char ch in s) 
    { 
     int x = Array.IndexOf(ta, ch); 

     if (x < 0) 
      return false; 

     ta[x] = '\0'; 
    } 

    return true; 
} 

Answer 5

要正確處理所有Unicode字符（因爲Char代表UTF-16代碼單元），所以我想不出一種有效的方法。但我會嘗試用正確之一：

public static bool isAnagram(String s, String t) 
{ 
    s = s.Normalize(); 
    t = t.Normalize(); 

    if (s == "" || t == "") return false; 
    else if (s.Length != t.Length) return false; 

    while (s.Length > 0) 
    { 
     char first = s[0]; 
     string search = new string(first, 1); 
     if (Char.IsHighSurrogate(first)) 
     { 
      char second = s[1]; //Assumed to work - if it doesn't, the input was malformed 
      search = new string(new char[] { first, second }); 
     } 
     int index = t.IndexOf(search); 
     if (index < 0) return false; 
     t = (index > 0 ? t.Substring(0, index) : "") + t.Substring(index + search.Length); 
     s = s.Substring(search.Length); 
    } 
    return true; 
} 

否則，如果你想繼續使用計數器陣列（letters），你應該使用可以包含至少1114112個元素的數組，你仍然需要正確處理代理人。

Answer 6

基於字典的解決方案。分解通過計算每個字符的字符串，然後做一個Dictionary comparaison（注意，此方法吹我的心）：

class Program 
{ 
    static void Main(string[] args) 
    { 
     Console.WriteLine("jon skeet".PermutationOf("jokes net")); 
     Console.WriteLine(new[] { 5, 2, 3, 4, 5 }.PermutationOf(new[] { 5, 4, 5, 2, 3 })); 
     Console.Read(); 
    } 
} 

public static class Extensions 
{ 
    public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2) 
    { 
     return source1.IsPermutationOf(source2, EqualityComparer<T>.Default); 
    } 
    public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2, EqualityComparer<T> comparer) 
    { 
     return source1.Decompose(comparer).DictionaryEqual(source2.Decompose(comparer)); 
    } 
    public static Dictionary<T, int> Decompose<T>(this IEnumerable<T> source, EqualityComparer<T> comparer) 
    { 
     return source.GroupBy(t => t, comparer).ToDictionary(t => t.Key, t => t.Count(), comparer); 
    } 
    public static bool DictionaryEqual<TKey, TValue>(this IDictionary<TKey, TValue> first, IDictionary<TKey, TValue> second) 
    { 
     return first.Count == second.Count && !first.Except(second).Any(); 
    } 
} 

請注意，你可以給一個自定義字符相等比較器，用於處理大/小寫問題。

我走了一點，通過重命名IsAnagram，IsPermutationOf。實際上適用於各種列表。這種方式非常有用和優雅。

Answer 7

正如您所要求的更優雅的解決方案，也許這一個適合您的需求 - 更緊密，寫成擴展方法：

public static bool IsAnagram(this string s1, string s2) 
{ 
    if (s1.Length == s2.Length) 
    { 
     var count = new int[1024]; 
     foreach (var c in s1) 
     { 
      ++count[c]; 
     } 
     return s2.All(t => --count[c] >= 0); 
    } 
    return false; 
} 

var result = "mary".IsAnagram("army"); 

Answer 8

1. 檢查長度相等，如果沒有，他們不字謎
2. 遍歷的t
3. 檢查的t當前字符存在於s，該字符如果沒有，他們沒有字謎
4. 如果是從s

5. 刪除字符如果結果爲空字符串他們字謎

   public static bool isAnagram(String s, String t) { 
       if(s.Length != t.Length) 
        return false; 
   
       for(int i = 0; i < t.Length; i++) 
       { 
        var n = s.IndexOf(t[i]); 
        if(n < 0) 
         return false; 
        s = s.Remove(n, 1); 
       } 
       return String.IsNullOrEmpty(s); 
   }