唯一長度順序子序列

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

難度：中

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

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

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

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

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

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

範例1：

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

範例2：

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

範例 3：

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

約束：

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

提示：

1. 長度為 3 的回文字串的最大數量是多少？
2. 我們如何追蹤出現在給定位置左側的字元？

解：

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

方法

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

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

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

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

讓我們用 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. 前綴數組:

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

2. 後綴數組:

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

3. 中間字元:

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

4. 雜湊映射:

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

複雜

• 時間複雜度：O(n)

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

• 空間複雜度：O(n)

  • 用於前綴和後綴數組。

輸出

程式碼為給定的範例產生正確的結果：

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

聯絡連結

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

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

• 領英
• GitHub

以上是唯一長度順序子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！