Biorąc pod uwagę dwa ciągi, jest jednym anagram drugiej

Question

Właśnie rozpoczął przeżywa „Cracking kodowania Wywiad” i mają następujące rozwiązanie tego problemu:

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; 
} 

to dość dużo verbatim rozwiązanie z książka, tylko w języku C#, nie Java i z dodatkowymi zerami kontrolnymi. Rozwiązałem też pytanie za pomocą LINQ, ale chciałem dodatkowego rozwiązania, które nie wymagałoby sortowania.

Czy to podejście może być nieco bardziej eleganckie? Kod działa dobrze, chcę tylko wiedzieć, czy istnieje bardziej eleganckie lub lepsze rozwiązanie. Dzięki!!

Answer 1

Kod ten powinien pracować dla Ciebie:

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); 
} 

Edit: Dodano non wersję linq.

Możesz również dodać dodatkowe kontrole dla wartości pustych i pustych i przenieść rozwiązanie do StringBuilder, aby poprawić wydajność, ale cel kodu jest jasny.

Answer 2

można sortować oba ciągi i porównać

Answer 3

sortowania a następnie porównanie sekwencji działa:

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

Alternatywnie, można użyć Dictionary<char, int> śledzić liczby znaków (znaków Unicode mieć więcej niż 256 możliwa wartość). Ponadto nie trzeba wywoływać połączenia z ToArray() przed iterowaniem znaków napisu.

Answer 4

Co powiesz na to rozwiązanie inne niż 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

Aby poprawnie obsłużyć wszystkie znaki Unicode (ponieważ Char reprezentuje jednostkę kodu UTF-16), nie mogę wymyślić skutecznego sposobu. Ale postaram się prawidłowego jednym:

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; 
} 

W przeciwnym razie, jeśli chcesz kontynuować z użyciem tablicy liczników (letters), powinieneś użyć tablicę, która może zawierać co najmniej 1114112 elementy, i nadal musisz właściwie przetwarzać surogaty.

Answer 6

Rozwiązanie oparte na słowniku. Rozkładać każdy łańcuch zliczając char, a następnie zrobić Dictionary comparaison (zauważ, że ta metoda blow zdanie):

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(); 
    } 
} 

pamiętać, że można dać zwyczaj char równości comparer, radzenia sobie z wielkimi/małymi literami problematyczne.

Poszedłem trochę dalej, zmieniając nazwę na IsAnagram, przez IsPermutationOf. Działa na wszystkich rodzajach list. Bardzo przydatne i eleganckie w ten sposób.

Answer 7

Jak można prosić o bardziej eleganckie rozwiązanie, być może ten pasuje do Twoich potrzeb - bardziej zagęszczony, napisane jako metodę rozszerzenia:

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. Sprawdź, czy długości są równe, jeśli nie, to nie są one anagram
2. Loop ciągu znaków z t
3. Sprawdź, czy obecny char z t istnieje w s, jeśli nie, to nie są one anagram
4. Jeśli więc usunąć ten char od s

5. Jeśli wynikiem jest pusty łańcuch są anagram

   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); 
   }