問題タブ [anagram]

私は最近、2 つの文字列が互いにアナグラムであるかどうかをチェックするアルゴリズムの設計を依頼されました。私の目標は、空間と時間の複雑さを最小限に抑えることだったので、次のアルゴリズムを思いつきました。

1. それぞれゼロに初期化された 26 要素の配列を作成します。
2. 最初の文字列をトラバースし、文字ごとに、その文字に対応する配列要素をインクリメントします。
3. 2 番目の文字列をトラバースし、文字ごとに、その文字に対応する配列要素をデクリメントします。
4. アレイ全体をスキャンします。すべての要素が 0 の場合、2 つの文字列はアナグラムです。

ただし、このアルゴリズムの時間の複雑さは O(n) であり、より複雑なアルゴリズムを思いつくことはできません。誰か知っていますか？

私はこれを使用して問題を解決しました（ひどく非効率的な方法）：

辞書で有効なアナグラムが最も多い5文字の単語を見つけるのに10分ほどかかりました。文字の制約のない単語でこれを実行したいのですが、ばかげた時間がかかります。これを最適化する方法はありますか？

JavaScript で単語のすべての可能なアナグラムのリストを作成するにはどうすればよいですか?この質問が既に尋ねられている場合は、答えを教えてください。

ありがとうございました

私は（Javaで）小さなプロジェクトを行っていますが、uniは自分自身をテストするためだけに出ており、つまずきにぶつかりました。

私は、辞書のテキストバージョンから読み込み、それをds（データ構造）に格納してから、ランダムな文字列（できれば意味のない文字列ですが、文字と-のみ）をユーザーに要求するプログラムを作成しようとしています。 、数字やその他の句読点はありません-私は他に何も興味がありません）、入力された文字列のすべてのアナグラムを見つけ、それを辞書dsと比較して、辞書にあるすべての可能なアナグラムのリストを返します。

さて、ステップ1と2（辞書からの読み取り）では、すべてを読み取るときに、マップに保存しました。キーはアルファベットの文字で、値はその文字で始まるすべての単語を格納するArrayListsです。 。

私はすべてのアナグラムを見つけることに固執し、可能な順列の数を再帰的に（誇らしげに）計算する方法を考え出しました。実際に再配置を行う方法がわかりません。

それをcharに分割してそのように遊ぶのが良いですか、それとも分割して文字列要素として保持するのが良いですか？さまざまなサイトでサンプルコードをオンラインで見たことがありますが、コードを見たくありません。このソリューションの開発の背後にあるアプローチ/アイデアの種類を知りたいと思います。

つまり、すべての順列を生成したら、辞書dsとの比較をどのように行うかを知っていると思います。

アドバイスは役に立ちますが、それでよければコードではなく、単なるアイデアです。

PSこれまでのところ（何らかの理由で）私のコードを見たい場合は、私が持っているものを投稿します。

これのバリエーションが以前に尋ねられたことは知っていますが、以前の実装のほとんどがセットと issubset メソッドを使用していたため、以前の実装を理解できませんでした。

これが私がやろうとしていることです: 私は辞書に単語のセットと可能な文字のリストを持っています. リスト内の文字を並べ替えることで、セットのメンバーを形成できるかどうかを調べたい. これが私の現在の実装です：

この実装の明らかな問題は、「文字」に複数の文字を使用する単語が見つかることです。たとえば、文字リストに「a」と「r」のコピーが 1 つしかないにもかかわらず、「cardboard」という単語は有効な単語として表示されます。リストで「issubset」メソッドを使用するにはどうすればよいですか?

単語リストと、多数のアナグラムを含むファイルがあります。これらのアナグラムは、単語リストにある単語です。一致する単語を見つけて出力ファイルに生成するアルゴリズムを開発する必要があります。これまでに開発したコードは、最初の 2 つの単語に対してのみ機能しました。さらに、コードのどこかに数字を含む文字列をうまく処理するコードを取得できません。コードを修正する方法を教えてください。

アナグラムと部分一致を見つけるためのモバイルアプリを作成しています。計算能力はそれほど多くなく、効率が重要であるため、モバイルは重要です。

アルゴリズムは、繰り返しを含む任意の数の文字を受け取り、すべての文字を1回だけ使用して、その文字から構成される最長の単語を検索します。私はまた、トップの結果をすばやく見つけることに興味があり、Nが満たされている限り、ボトム（短いもの）にはあまり関心がありません。例えば：

私はいくつかのグーグルを行い、いくつかのアルゴリズムを見つけました。そして、効率的だと思ったものを思いつきましたが、私が望むほど効率的ではありません。

ソートされたキーをそのキーを生成する実際の単語にマップするルックアップ辞書が事前に作成されています。

キーの長さに基づいて、各辞書をさらに別の辞書に分割しました。したがって、5文字の長さのキーはある辞書にあり、6文字のキーは別の辞書にあります。これらの各ディクショナリは配列内にあり、インデックスはディクショナリで見つかったキーの長さです。

私のアルゴリズムは、入力単語 " lappe"を取得することから始まり、それをソートします。

ここで、最大5文字の内容を持つ辞書ごとに、比較して引き出します。擬似コードは次のとおりです。

辞書には約17万語しか含まれていませんが、12文字の入力で検索に最大20秒かかります。私のmatch方法では、キーから正規表現を作成します。

たとえば、acst（acts）などの4文字のキーは、次のackst理由で（stack）と一致します。

私は他のアプリがはるかに短い時間で同じことをするのを見てきました、そして私のアプローチがゴミなのか、それとも単に微調整が必​​要なのか疑問に思います。

最大長でソートされた単語から上位N個のアナグラムを生成するための最大の計算効率を得るにはどうすればよいですか？

非常に基本的な手続き型アプローチを使用して、アナグラム ソルバーを作成しようとしています。おそらくクラスを使用してこれを行うべきだったことがわかりましたが、今では遅すぎて、割り当ての期限が近づいています。これを理解する方法についての提案は素晴らしいでしょう!

基本的に、これはアルゴリズムが行うべきことです。

1. 辞書内のすべての単語を取得します。それらをコンテナに保管する
2. ユーザーから言葉をもらいます。必要に応じて終了
3. ユーザーが入力した単語の順列をすべて取得します
4. ユーザーが入力した単語を順列から取り除きます
5. パート 1 で収集した辞書にも含まれていない順列コレクションのすべての単語を削除します

最後のステップとして、重複したアナグラム (つまり、「ループ」などの同じ文字を含むアナグラム) を表示しないようにする必要があります。このチェックを機能させることができないようです。これは、以下の TODO コメント ブロックの下に記載されています。

どんな提案も素晴らしいでしょう!!

プログラムを実行しようとするたびに、「アナグラム」が表示され、プログラムを実行できません。どうすれば消えますか？ありがとう

両方の文字列を O(nlogn) 時間で並べ替えた後、2 つの文字列がアナグラムであるかどうかを見つけることができますが、o(n) 時間と O(1) 空間でそれを見つけることは可能です。