句子相似度 III

1813。句子相似度 III

難度：中

主題：陣列、兩個指標、字串

給你兩個字串sentence1和sentence2，每個字串代表一個由單字組成的句子。句子是單字的列表，由單一空格分隔，沒有前導或尾隨空格。每個單字僅由大寫和小寫英文字元組成。

兩個句子 s1 和 s2 被認為相似，如果可以在其中一個句子中插入任意句子（可能為空），使得兩個句子變得相等。 注意插入的句子必須與現有單字之間以空格分隔。

例如，

• 透過在 s1 中的“Hello”和“Jane”之間插入“my name is”，可以使 s1 =“Hello Jane”和 s2 =“Hello my name is Jane”相等。
• s1 =“Frog Cool”和 s2 =“Frogs are Cool”並不相似，因為雖然 s1 中插入了一個句子“s are”，但它與“Frog”之間沒有空格分隔。

給定兩個句子sentence1和sentence2，如果sentence1和sentence2相似，則回傳true。否則，回傳 false.

範例1：

• 輸入：句子1 =“我的名字是海莉”，句子2 =“我的海莉”
• 輸出： true
• 解釋：透過在“My”和“Haley”之間插入“name is”，可以將句子2變成句子1。

範例2：

• 輸入：句子1 =“的”，句子2 =“很多單字”
• 輸出： false
• 解釋： 不能在其中一個句子中插入單一句子以使其與另一個句子相等。

範例 3：

• 輸入：句子1 =“現在吃飯”，句子2 =“吃飯”
• 輸出： true
• 說明：在句尾插入「right now」可以將sentence2變成sentence1。

約束：

• 1
• 句子1和句子2由小寫和大寫英文字母和空格組成。
• sentence1和sentence2中的單字用一個空格分隔。

提示：

1. 查看它的一種方法是找到一個句子作為另一個句子的前綴和後綴的串聯。
2. 取得它們之間的最長公共前綴和最長公共後綴。

解：

我們可以透過比較兩個句子的最長公共前綴和後綴來接近它。如果一個句子的剩餘部分中的單字完全包含在另一個句子中（可能是空的），那麼這些句子可以被認為是相似的。

步驟：

1. 將兩個句子分成單字數組。
2. 使用兩個指標比較兩個陣列開頭的最長公共前綴。
3. 使用另外兩個指標來比較兩個陣列末尾的最長公共後綴。
4. 比較公共前綴和後綴後，如果其中一個句子中剩餘的單字形成一個空數組（意味著它們都已匹配），則認為句子相似。

讓我們用 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分別是sentence1和sentence2的長度。這是因為我們在檢查公共前綴和後綴時僅處理兩個句子中的單字一次。

考慮到限制，該解決方案應該能夠有效地工作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是句子相似度 III的詳細內容。更多資訊請關注PHP中文網其他相關文章！