6

我刚刚开始阅读“Cracking the Coding Interview”，并为这个问题提供了以下解决方案：

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 解决了这个问题，但想要一个不涉及排序的附加解决方案。

可以使这种方法更优雅吗？代码工作得很好，我只想知道是否有更优雅或更好的解决方案。谢谢！！

4

8 回答 8

16

此代码应该适合您：

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 版本。

您还可以为 null 和空值添加一些额外的检查，并将解决方案移至 StringBuilder 以提高性能，但代码的意图很明确。

于 2013-04-22T07:47:51.803 回答
4

当您要求更优雅的解决方案时，也许这个解决方案适合您的需求 - 更紧凑，编写为扩展方法：

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");
于 2013-04-22T07:59:24.403 回答
3

要正确处理所有 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 个元素的数组，并且您仍然需要正确处理代理项。

于 2013-04-22T07:50:17.493 回答
2

您可以对两个字符串进行排序并进行比较

于 2013-04-22T07:32:56.177 回答
2

这个非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;
}
于 2013-04-22T07:44:39.057 回答
1

基于字典的解决方案。通过计算字符来分解每个字符串，然后进行字典比较（请注意，这种方法让我大吃一惊）：

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

请注意，您可以提供自定义 char 相等比较器，用于处理大写/小写问题。

我更进一步，将 重命名IsAnagram为IsPermutationOf。实际上适用于各种列表。这种方式非常有用和优雅。

于 2013-04-22T07:54:25.743 回答
1
  1. 检查长度是否相等，如果不相等，则它们不是字谜
  2. 循环遍历的字符t
  3. 检查当前 char 是否t存在于 中s，如果不存在，则它们不是 anagram
  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);
}
于 2013-04-22T07:59:56.057 回答
0

排序然后比较序列工作：

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

或者，您可以使用 aDictionary<char, int>来跟踪字符计数（Unicode 字符有超过 256 个可能的值）。ToArray()此外，在迭代字符串的字符之前，您不需要调用 to 。

于 2013-04-22T07:34:42.690 回答