検索

文の類似性Ⅲ

Oct 07, 2024 am 06:08 AM

Sentence Similarity III

1813年。文の類似性 III

難易度:

トピック: 配列、2 つのポインター、文字列

文 1 と文 2 の 2 つの文字列が与えられ、それぞれ単語で構成される を表します。文は、単一のスペースで区切られ、先頭または末尾のスペースがない単語のリストです。各単語は英大文字と小文字のみで構成されています。

2 つの文 s1 と s2 は、これら 2 つの文が等しくなるようにこれらの文の 1 つに任意の文 (空の可能性があります) を挿入できる場合、類似とみなされます。 挿入する文はスペースで既存の単語と区切る必要があることに注意してください

たとえば、

  • s1 = "Hello Jane" と s2 = "Hello my name is Jane" は、s1 の "Hello" と "Jane" の間に "my name is" を挿入することで等しくすることができます。
  • s1 = 「カエルかっこいい」と s2 = 「カエルかっこいい」は、s1 に「s は」という文が挿入されていますが、「カエル」とスペースで区切られていないため、似ていません。

文 1 と文 2 の 2 つの文が与えられた場合、文 1 と文 2 が 似ている場合、を返します。それ以外の場合は、falseを返します。

例 1:

  • 入力: 文 1 = "私の名前はヘイリーです"、文 2 = "私のヘイリー"
  • 出力: true
  • 説明: 文 2 は、「My」と「Haley」の間に「name is」を挿入することで、文 1 に変えることができます。

例 2:

  • 入力: 文 1 = 「の」、文 2 = 「たくさんの単語」
  • 出力: false
  • 説明: 一方の文の中に単一の文を挿入して、もう一方の文と等しくすることはできません。

例 3:

  • 入力: 文 1 = "今食べています"、文 2 = "食べています"
  • 出力: true
  • 説明: 文 2 は、文の最後に「今」を挿入することで文 1 に変えることができます。

制約:

  • 1
  • 文 1 と文 2 は、小文字と大文字の英字とスペースで構成されます。
  • 文 1 と文 2 の単語は 1 つのスペースで区切られています。

ヒント:

  1. これを調べる 1 つの方法は、ある文を他の文の接頭辞と接尾辞の連結として見つけることです。
  2. それらの間の最長の共通プレフィックスと最長の共通サフィックスを取得します。

解決策:

両方の文に共通する最長の接頭辞と接尾辞を比較することでそれにアプローチできます。 1 つの文の残りの部分の単語がもう 1 つの文に完全に含まれている (おそらく空である) 場合、その文は類似していると見なすことができます。

手順:

  1. 両方の文を単語の配列に分割します。
  2. 2 つのポインターを使用して、両方の配列の先頭から最も長い共通プレフィックスを比較します。
  3. 別の 2 つのポインターを使用して、両方の配列の末尾から最も長い共通のサフィックスを比較します。
  4. 共通の接頭辞と接尾辞を比較した後、文の 1 つの残りの単語が空の配列を形成する場合 (つまり、すべてが一致した場合)、文は類似していると見なされます。

このソリューションを PHP で実装してみましょう: 1813。文の類似性 III


<p><?php <br>
/**</p>

  • @param String $sentence1
  • @param String $sentence2
  • @return Boolean / function areSentencesSimilar($sentence1, $sentence2) { ... ... ... /*
    • go to ./solution.php */ }

// Test examples
$sentence1 = "My name is Haley";
$sentence2 = "My Haley";
echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true

$sentence1 = "of";
$sentence2 = "A lot of words";
echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: false

$sentence1 = "Eating right now";
$sentence2 = "Eating";
echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true
?>




説明:

  1. 文を単語に分割する: 文の文字列を単語の配列に分割するには、explode() を使用します。
  2. 共通の接頭辞の比較: 両方の配列を最初から繰り返し、対応する単語を比較します。単語が一致する限りループは続きます。
  3. 共通の接尾辞の比較: 両方の配列の末尾の単語を比較し、再度ループを使用して一致する単語をチェックします。
  4. 最終チェック: 共通の接頭辞と接尾辞を処理した後、一致した単語の数 (接頭辞接尾辞) が短い文内のすべての単語をカバーしているかどうかを確認します。そうであれば、文は類似していると考えられます。

時間計算量:

  • 時間計算量は O(n m) です。ここで、n と m はそれぞれセンテンス 1 とセンテンス 2 の長さです。これは、共通の接頭辞と接尾辞をチェックしながら、両方の文の単語を 1 回だけ処理するためです。

このソリューションは、制約を考慮すると効率的に機能するはずです。

連絡先リンク

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

以上が文の類似性Ⅲの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
誇大広告を超えて:今日のPHPの役割の評価誇大広告を超えて:今日のPHPの役割の評価Apr 12, 2025 am 12:17 AM

PHPは、特にWeb開発の分野で、最新のプログラミングで強力で広く使用されているツールのままです。 1)PHPは使いやすく、データベースとシームレスに統合されており、多くの開発者にとって最初の選択肢です。 2)動的コンテンツ生成とオブジェクト指向プログラミングをサポートし、Webサイトを迅速に作成および保守するのに適しています。 3)PHPのパフォーマンスは、データベースクエリをキャッシュおよび最適化することで改善でき、その広範なコミュニティと豊富なエコシステムにより、今日のテクノロジースタックでは依然として重要になります。

PHPの弱い参照は何ですか、そしていつ有用ですか?PHPの弱い参照は何ですか、そしていつ有用ですか?Apr 12, 2025 am 12:13 AM

PHPでは、弱い参照クラスを通じて弱い参照が実装され、ガベージコレクターがオブジェクトの回収を妨げません。弱い参照は、キャッシュシステムやイベントリスナーなどのシナリオに適しています。オブジェクトの生存を保証することはできず、ごみ収集が遅れる可能性があることに注意する必要があります。

PHPで__invoke Magicメソッドを説明してください。PHPで__invoke Magicメソッドを説明してください。Apr 12, 2025 am 12:07 AM

\ _ \ _ Invokeメソッドを使用すると、オブジェクトを関数のように呼び出すことができます。 1。オブジェクトを呼び出すことができるように\ _ \ _呼び出しメソッドを定義します。 2。$ obj(...)構文を使用すると、PHPは\ _ \ _ Invokeメソッドを実行します。 3。ロギングや計算機、コードの柔軟性の向上、読みやすさなどのシナリオに適しています。

同時性については、PHP 8.1の繊維を説明します。同時性については、PHP 8.1の繊維を説明します。Apr 12, 2025 am 12:05 AM

繊維はPhp8.1で導入され、同時処理機能が改善されました。 1)繊維は、コルーチンと同様の軽量の並行性モデルです。 2)開発者がタスクの実行フローを手動で制御できるようにし、I/O集約型タスクの処理に適しています。 3)繊維を使用すると、より効率的で応答性の高いコードを書き込むことができます。

PHPコミュニティ:リソース、サポート、開発PHPコミュニティ:リソース、サポート、開発Apr 12, 2025 am 12:04 AM

PHPコミュニティは、開発者の成長を支援するための豊富なリソースとサポートを提供します。 1)リソースには、公式のドキュメント、チュートリアル、ブログ、LaravelやSymfonyなどのオープンソースプロジェクトが含まれます。 2)StackOverFlow、Reddit、およびSlackチャネルを通じてサポートを取得できます。 3)開発動向は、RFCに従うことで学ぶことができます。 4)コミュニティへの統合は、積極的な参加、コード共有への貢献、および学習共有への貢献を通じて達成できます。

PHP対Python:違いを理解しますPHP対Python:違いを理解しますApr 11, 2025 am 12:15 AM

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHPは、シンプルな構文と高い実行効率を備えたWeb開発に適しています。 2。Pythonは、簡潔な構文とリッチライブラリを備えたデータサイエンスと機械学習に適しています。

PHP:それは死にかけていますか、それとも単に適応していますか?PHP:それは死にかけていますか、それとも単に適応していますか?Apr 11, 2025 am 12:13 AM

PHPは死にかけていませんが、常に適応して進化しています。 1)PHPは、1994年以来、新しいテクノロジーの傾向に適応するために複数のバージョンの反復を受けています。 2)現在、電子商取引、コンテンツ管理システム、その他の分野で広く使用されています。 3)PHP8は、パフォーマンスと近代化を改善するために、JITコンパイラおよびその他の機能を導入します。 4)Opcacheを使用してPSR-12標準に従って、パフォーマンスとコードの品質を最適化します。

PHPの未来:適応と革新PHPの未来:適応と革新Apr 11, 2025 am 12:01 AM

PHPの将来は、新しいテクノロジーの傾向に適応し、革新的な機能を導入することで達成されます。1)クラウドコンピューティング、コンテナ化、マイクロサービスアーキテクチャに適応し、DockerとKubernetesをサポートします。 2)パフォーマンスとデータ処理の効率を改善するために、JITコンパイラと列挙タイプを導入します。 3)パフォーマンスを継続的に最適化し、ベストプラクティスを促進します。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

WebStorm Mac版

WebStorm Mac版

便利なJavaScript開発ツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター