アナグラム

by

ほーらい! この記事で、この講座のこのセクションでの最後の文字列操作の挑戦となります。 長い道のりでしたね！

この課題では、JavaScriptでアナグラムを検出する2つの方法について考えます。

アナグラムとは何か？

それぞれの文字を 1 回だけ使用して他の単語の文字を並べ替えることによって形成できるとき、単語は他の単語のアナグラムであると言われます。 例: listen は silent のアナグラムです。

Let’s get busy, you shall be already have your development environment setup for this course. git pull コマンドを実行して、クローンしたリポジトリを更新します。 Beginner フォルダの中の isAnagram フォルダに移動してください。 この課題のための作業はここで行います。

課題

Given two strings, write an algorithm to check if they are anagrams of each other.この課題は、index-START.js ファイルでフォローされていることを確認します。 テストに合格した場合は真を、不合格の場合は偽を返せ。 例：

isAnagram('silent', 'listen') // should return true

Algorithmic Thinking

この課題を解決するために、2つのパラメータ、つまり比較する2つの文字列を受け取る関数を書きます。

BeginnerTailwind.com ゼロから学ぶTailwind CSS

関数内で、両方の言葉を比較して同じ回数使われた文字が含まれているか確認します。 エラーを回避するために、文字列をサニタイズし、不要な文字やスペースを取り除きます。

また、大文字小文字の違いによるエラーを避けるために、比較を行う前にすべての文字を共通の文字ケースに変換しています。 両方の単語が同じ長さであることを確認することも、有効な比較の主な要因であるため、非常に重要です。

コード実装

ここで、上記のアルゴリズム論理に従って、ソリューションを実装する 2 つの方法を検討します。

  • 直接比較
  • 文字マップ比較

直接比較

この方法では、2つのパラメーター、つまり比較される2つの文字列を受け取る関数を定義することにします。

Cleaning Up the String文字列をクリーンアップするために、sanitizeString関数を作成します。 この関数は、サニタイズする文字列をパラメーターとして受け取り、.toLowerCase()、.replace()、.split()、.sort()、.join() メソッドを使用して、次のように文字列を操作します：

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

少し分解します：

  • 最初に、.toLowerCase()メソッドを使用して、文字列全体を小文字に変換します。
  • 次に、.replace() メソッドを使用して、指定された正規表現パターンを使用して文字列を検索し、アルファベット以外のすべての文字を空文字列に置き換えます。 これで、文字だけが残ることになります。
  • 次に、.split() を呼び出して文字列を文字の配列に分割します。
  • .sort()メソッドを使用して、配列内の文字（要素）をアルファベット順に並べ替えます。

この文字列は、サニタイズされた文字列として返されるものです。 次に、sanitizeString 関数を使用して受け取った文字列を単純にクリーンアップし、その結果を比較します。 両方の文字列が一致した場合、アナグラムとして通過したことを意味するtrueを返す。

以下の完全な解答を参照してください： 

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

One down! 3032>

文字マップの比較

このアプローチでは、まず createCharMap 関数を使用して文字マップを生成します。

キャラクタ マップとは何ですか。

この文脈で使用されるように、キャラクタ マップ オブジェクトは、文字列内のすべての文字を、その文字列内で発生する回数にマッピングするオブジェクトです。

文字マップの作成以下の createCharMap 関数では、受け取った文字列の各文字を繰り返し処理するために for…of ループを使用します。

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

各文字について、.hasOwnProperty()メソッドを使用して文字マップ charMap にすでにプロパティとして存在しているかどうかを確認します。 存在する場合は値をインクリメントし、存在しない場合はその文字をプロパティとして追加し、値を 1 に設定します。

最後に、文字マップオブジェクトである charMap を返します。

文字マップの比較文字マップを生成する方法がわかったので、次のステップでは、以下の完全なソリューションに示すように、両方の文字列の文字マップを比較します： 

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

最初に、両方の文字列の長さが同じかを確認することに注意してください。 もし等しくなければ、falseを返す。これは、両者が決してアナグラムになり得ないことを示す指標である。

次に for…in ループを使って stringAMap のすべての文字と値を stringBMap の対応する文字と比較する。 もし一致しない値があれば、文字列がアナグラムでないことを示すために false を返す。 しかし、すべての値が一致した場合はテストに合格し、テストした文字列が確かにアナグラムであることを示す true を返す。

できました。 確かに長い実装ですが、より説明的なものであることは間違いありません。

Lets run our tests now, shall we?

Testing Correctness with Jest

上記の各ソリューションをテストするには、ターミナルから次のコマンドを実行します:

npm run test isAnagram

  • 直接比較

  • 文字マップ比較

我々は常に素晴らしいことをしていると見えます！

JSPerf によるパフォーマンスのテスト

ここで、パフォーマンス テストを実行して、どのソリューションがより速いかを判断します。

結果から、次のことがわかります。

より速い実装は、文字マップ比較手法と直接比較手法ですが、簡潔は約 52% 遅くなります。

** 意外でしょう？ メトリクスは決して嘘をつきません！**

実践的なアプリケーション

上で検討したアルゴリズムは、さまざまな方法で適用することができます。 これらは以下の通りです。

  • 暗号化
  • パスワード生成
  • 信頼できるタイムスタンプ
  • インタビューの符号化
  • ニーモニックの生成
  • ワードゲーム

    結論

以上のテクニックと概念を考慮しながらも、このようなことをやっています。 文字列を操作してアナグラムであるかどうかを判断するための貴重な方法を学んだ。 また、この知識を直接活用できる様々な分野についても検討した。

パフォーマンス テストを実行した結果、この問題を解決するための最も最適なアプローチは文字マップ比較法であると結論付けることができます。

参考資料

上記で取り上げた概念やテクニックについてさらに学ぶには、次のリンクを参照してください：

  • Regular Expressions
  • .replace()
  • .split()
  • .sort()
  • .join()
  • .hasOwnProperty()
  • For…of vs for…in loop

配列操作のアルゴリズムに焦点を当てた次の記事でお会いしましょう！✌🏿

この記事と同じですか？ Twitterで@worldclassdevをフォロー

コメントする