4

アナグラムが隣り合っている文字列の配列をソートする方法は?

例えば：

入力 {神、犬、abc、タクシー、人}
出力 {abc、タクシー、犬、神、人}

私のアプローチ：O（nlogn）で（アナグラムのケースを考慮せずに）配列をソートします。次に、最初の文字列を取得して文字列のヒストグラムを作成し、ヒストグラムを配列内の残りの文字列ヒストグラムと比較し、一致する文字列を配列の適切な位置に配置します..配列サイズに達するまで繰り返します..このアルゴリズムO（n ^ 3）の最悪のケース（最悪の場合、各文字列のサイズもnであると仮定した場合）とヒストグラム表現用の余分なスペースを取ります

ref から取得したヒストグラム アプローチ: 2 つの単語が互いのアナグラムであるかどうかを調べる

これよりもうまくできるでしょうか？

4

9 に答える 9

13

あなたは確かに次のようにもっとうまくやることができます：

  1. 文字列の配列をループする
  2. 各文字列について、最初にその文字をソートし、ソートされた文字列をキーとして元の文字列を値として使用し、ハッシュ テーブルに入れます。キーがソートされた文字列であり、値がすべてアナグラムであるハッシュテーブルが作成されますが、これらの値は順序付けられています。map<string, set<string> >この目的のために使用することができます。
  3. ハッシュテーブルを反復処理し、指定されたキーのすべてのアナグラムを一緒に出力します。それらは互いに隣り合っている必要があります

文字列の長さが M で、配列のサイズが N であると仮定すると、時間の複雑さは次のようになります: O(NMlogM)、M は通常平均で N よりも小さくなります。したがって、これはあなたが言ったことよりもはるかに効率的です。

于 2013-03-20T04:55:40.057 に答える
3 
#include <vector>
#include <unordered_map>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

vector<string> sort_string_anagram(vector<string> array)
{
    unordered_map<string, set<string>> anagram;

    for(string word : array)
    {
      string sorted_word(word);

      sort(sorted_word.begin(),sorted_word.end());

      anagram[sorted_word].insert(word);
    }

    sort(array.begin(), array.end());

    vector<string> result;

    for(string word : array)
    {
        unordered_map<string,set<string>>::iterator iter;

        string sorted_word(word);

        sort(sorted_word.begin(), sorted_word.end());

        if( (iter = anagram.find(sorted_word)) != anagram.end() )
        {
           for(set<string>::iterator it = (iter->second).begin(); it!= (iter->second).end();++it)
           {
              result.push_back(*it);
           }
           anagram.erase(iter);
        }
    }
    return result;
}

@Jitendard、@taocp、時間の複雑さを持つ完全なソリューション: O( N(MlogM) + NlogN + N(MlogM + A) )。N は配列サイズ、M は単語サイズ、A は単語に対して存在するアナグラムの最大数です。

于 2016-04-23T22:05:35.470 に答える
1

@Song Wang : 私もそうしようと思っていました。しかし、ハッシュマップから文字列を取り出した後、文字列を配置する順序をどうやって知るのでしょうか?
K1 = "abc", V1 = "cab"
K2 = "abc", V2 = "abc"を抽出するとします
。リスト 1 または 2 のどちらを最初に配置するかをどのように判断しますか?
たぶん、それらをもう一度並べ替えます。しかし、それは複雑さのために悪いでしょう。

于 2013-03-20T07:00:42.347 に答える
0

インターネットから解決策を見つけました：

public static void sortStringWithAnagrams(String[] stringArray) {
    Arrays.sort(stringArray, new AnagramComparator());
}

public static class AnagramComparator implements Comparator<String> {

    public String getSortedString(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }

    public int compare(String s1, String s2) {
        return getSortedString(s1).compareTo(getSortedString(s2));
    }

}
于 2016-11-26T12:00:07.997 に答える
0

そもそもなぜソートするのか？アナグラムに基づいて配列をサブセットに分割することはできません。サブセットを並べ替え、最終的に各サブセットの最初の単語に基づいてマージします。

于 2013-03-20T04:32:11.970 に答える