字串中的額外字符

2707。字串中的額外字元

難度：中

主題：陣列、雜湊表、字串、動態規劃、Trie

給你一個 0 索引的 字串 s 和一個單字字典。您必須將 s 分成一個或多個非重疊子字串，以便每個子字串都出現在字典中。 s 中可能有一些額外字元，這些字元不存在於任何子字串中。

傳回如果您以最佳方式分解 s，則剩餘的最小剩餘額外字元數。

範例1：

• 輸入： s = "leetcode",dictionary = ["leet","code","leetcode"]
• 輸出： 1
• 解釋： 我們可以將 s 分成兩個子字串：從索引 0 到 3 的「leet」和從索引 5 到 8 的「code」。只有 1 個未使用的字元（在索引 4 處），因此我們傳回 1 .

範例2：

• 輸入： s = "sayhelloworld",dictionary = ["hello","world"]
• 輸出： 3
• 解釋： 我們可以將 s 分成兩個子字串：從索引 3 到 7 的「hello」和從索引 8 到 12 的「world」。索引 0、1、2 處的字元不會在任何子字串中使用，並且因此被視為額外字元。因此，我們返回 3。

約束：

• 1
• 1
• 1
• 字典[i]和s僅由小寫英文字母組成
• 字典包含不同的單字

提示：

1. 我們可以在這裡使用動態規劃嗎？
2. 定義 DP[i] 為最優分解 s[0:i] 的最小額外字元。

解：

我們可以定義一個 dp 數組，其中 dp[i] 表示子字串 s[0:i] 經過最優切分後的最少多餘字元數。

方法：

1. 動態規劃定義：

   • 設 dp[i] 為子字串 s[0:i] 中額外字元的最少數量。
   • 為了計算 dp[i]，我們可以：
     • 將字元 s[i-1] 視為額外字元並移至下一個索引。
     • 或檢查字典中是否存在以索引 i 結尾的子字串，如果存在，則使用它來減少多餘的字元。

2. 過渡：

   • 對於每個索引 i，我們可以：
     • 如果我們將 s[i] 視為額外字符，則將 dp[i-1] 加一。
     • 檢查每個可能的子字串 s[j:i]（對於 j

3. 結果：

   • dp[len(s)] 的值將為我們提供整個字串 s 中額外字元的最少數量。

讓我們用 PHP 實作這個解決方案：2707。字串中的額外字元

<?php
/**
 * @param String $s
 * @param String[] $dictionary
 * @return Integer
 */
function minExtraChar($s, $dictionary) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minExtraChar("leetscode", ["leet","code","leetcode"]); // Output: 1
echo "\n";
echo minExtraChar("sayhelloworld", ["hello","world"]); // Output: 3
?>

解釋：

1. 基本案例：

   • dp[0] = 0，因為空字串中不存在多餘字元。

2. 字典查找：

   • 我們使用 array_flip() 將字典單字儲存在雜湊映射中，以進行常數時間查找。

3. 過渡：

   • 對於每個位置 i，我們檢查所有可能的子字串 s[j:i]。如果字典中存在子字串，我們就更新 dp[i] 值。

4. 時間複雜度：

   • 時間複雜度為 O(n^2)，其中 n 是字串 s 的長度，因為對於每個索引，我們檢查所有先前的索引以形成子字串。

測試結果：

對於帶有字典 ["leet","code","leetcode"] 的輸入“leetscode”，函數正確傳回 1，因為只剩下 1 個額外字元 ("s")。

對於帶有字典 ["hello","world"] 的輸入“sayhelloworld”，函數傳回 3，因為前三個字元（“say”）是額外的。

聯絡連結

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

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

• 領英
• GitHub

以上是字串中的額外字符的詳細內容。更多資訊請關注PHP中文網其他相關文章！