6

「コーディングインタビューのクラック」を始めたばかりで、この問題に対する次の解決策があります。

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

これは、Java ではなく C# のみであり、いくつかの追加の nullchecks を備えた、本からのほぼそのままのソリューションです。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 文字 (UTF-16 コード単位を表すため) を適切に処理するCharには、効率的な方法が思い浮かびません。しかし、私は正しいもので試してみます:

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. の現在の文字が に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);
}
于 2013-04-22T07:59:56.057 に答える
0

シーケンスを並べ替えてから比較すると、次のようになります。

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

あるいは、 a を使用しDictionary<char, int>て文字数を追跡することもできます (Unicode 文字には 256 を超える値があります)。ToArray()また、文字列の文字を反復処理する前に を呼び出す必要はありません。

于 2013-04-22T07:34:42.690 に答える