文の類似性Ⅲ

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>

<ul>
<li>@param String $sentence1</li>
<li>@param String $sentence2</li>
<li>@return Boolean
<em>/
function areSentencesSimilar($sentence1, $sentence2) {
...
...
...
/</em>*

<ul>
<li>go to ./solution.php
*/
}
</li>
</ul>
</li>
</ul>

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

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

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

説明:

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 サイトの他の関連記事を参照してください。