1930。唯一長度為 3 的回文子序列

難度：中

主題：雜湊表、字串、位元操作、前綴和

給定一個字串 s，傳回作為 s 的 子序列的長度為三的唯一回文數(shù)的數(shù)量。

注意即使有多種方式獲得同一個子序列，仍然只計算一次。

回文是一個向前和向後讀取相同的字串。

字串的子序列是在原始字串中刪除一些字元（可以沒有）而產(chǎn)生的新字串，而不改變剩餘字元的相對順序。

• 例如，「ace」是「abcde」的子序列。

範(fàn)例1：

• 輸入： s = "aabca"
• 輸出： 3
• 解釋： 長度為 3 的 3 個回文子序列是：
  • 「aba」（「aabca」的子序列）
  • 「aaa」（「aabca」的子序列）
  • 「aca」（「aabca」的子序列）

範(fàn)例2：

• 輸入： s = "adc"
• 輸出： 0
• 解釋：「adc」中不存在長度為 3 的回文子序列。

範(fàn)例 3：

• 輸入： s = "bbcbaba"
• 輸出： 4
• 解釋： 4 個長度為 3 的回文子序列是：
  • 「bbb」（「bbcbaba」的子序列）
  • 「bcb」（「bbcbaba」的子序列）
  • 「bab」（「bbcbaba」的子序列）
  • 「aba」（「bbcbaba」的子序列）

約束：

• 3 5
• s 僅由小寫英文字母組成。

提示：

1. 長度為 3 的回文字串的最大數(shù)量是多少？
2. 我們?nèi)绾巫粉櫝霈F(xiàn)在給定位置左側(cè)的字元？

解：

我們可以使用一種高效的演算法，利用前綴和後綴字元追蹤來計算所有有效的回文子序列。

方法

1. 追蹤字首:
   使用數(shù)組儲存字串中每個位置左側(cè)遇到的字元集。這將有助於有效地檢查一個字元是否可以構(gòu)成回文子序列的第一部分。

2. 曲目後綴字元:
   使用另一個陣列來儲存字串中每個位置右側(cè)遇到的字元集。這將有助於有效地檢查一個字元是否可以構(gòu)成回文子序列的第三部分。

3. 計算回文子序列:
   對於字串中的每個字符，將其視為長度為 3 的回文串的中間字符。檢查前綴和後綴字元的所有有效組合以確定唯一的回文。

4. 商店結(jié)果：
   使用雜湊集儲存唯一的回文子序列，確保不重複。

讓我們用 PHP 實作這個解：1930。唯一長度為 3 的回文子序列

<?php
/**
 * @param String $s
 * @return Integer
 */
function countPalindromicSubsequence($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

解釋：

1. 前綴數(shù)組:

   • 對於位置 i 處的每個字符，prefix[i] 儲存索引 i 之前遇到的所有不同字符。

2. 後綴數(shù)組:

   • 對於位置 i 處的每個字符，suffix[i] 儲存索引 i 之後遇到的所有不同字符。

3. 中間字元:

   • 將每個字元視為回文串的中間。對於與中間字元相符的每個前綴和後綴字元的組合，形成一個長度為 3 的回文。

4. 雜湊映射:

   • 使用關(guān)聯(lián)數(shù)組 ($uniquePalindromes) 儲存唯一的回文，確保不計算重複項。

複雜

• 時間複雜度：O(n)

  • 遍歷字串兩次來計算前綴和後綴數(shù)組。
  • 第三次遍歷檢查有效的回文子序列。

• 空間複雜度：O(n)

  • 用於前綴和後綴數(shù)組。

輸出

程式碼為給定的範(fàn)例產(chǎn)生正確的結(jié)果：

• 輸入: "aabca" → 輸出: 3
• 輸入: "adc" → 輸出: 0
• 輸入：「bbcbaba」→ 輸出：4

聯(lián)絡(luò)連結(jié)

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

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是唯一長度順序子序列的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！