推 koy784512: 大師 09/02 21:29
推 devilkool: 大師 dp問題都好難 09/02 21:36
→ Che31128: dp大師 09/02 21:42
https://leetcode.com/problems/extra-characters-in-a-string/description/
2707. Extra Characters in a String
給你一個字串 s 和一個字串陣列 dictionary 表示字典的值，我們要把 s 切分成
多個子字串且每個子字串都包含在 dictionary 之中，若子字串不包含我們需刪除他
，求出最少刪除幾個字元可以滿足條件。
Example 1:
Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and
"code" from index 5 to 8. There is only 1 unused character (at index 4), so
we return 1.
Example 2:
Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and
"world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in
any substring and thus are considered as extra characters. Hence, we return 3.
思路：
1.令 dp[i] 表示長度為 i 的字串的最小刪除數量，我們需找出子字串的轉移方程。
2.首先 dp[0] = 0 ，因為字串中沒有任何字元需要刪除。
3.再來對於字串 s[i] ，根據定義，他更新的位置會是 dp[i + 1]，有兩種情境：
字串 s[i] 結尾的某個子字串包含在字典，因為不需要刪除，所以他的成本 =
dp[j] (j為最佳切法的子字串開頭)
字串 s[i] 是多餘的字元，他的成本 = dp[i - 1] + 1
4.先把字典的值儲存在 Map 或字典表
5.我們從第一個字元開始遍歷，每次都把該字元當子字串尾部，並檢查
是否在字典裡，是的話就不斷更新 dp 的值：
dp[i + 1] = MIN(dp[i] + 1, dp[j1], dp[j2], ...)
* dp[j] 表示包含在字典裡的子字串
6.最後返回 dp[n] 即可
Java Code：
----------------------------------------------------------
class Solution {
public int minExtraChar(String s, String[] dictionary) {
Set<String> set = new HashSet<>();
set.addAll(Arrays.asList(dictionary));
int n = s.length();
int[] dp = new int[n + 1];
for (int i = 0; i < n; i++) {
dp[i + 1] = dp[i] + 1;
for (int j = 0; j <= i; j++) {
String subStr = s.substring(j, i + 1);
if (set.contains(subStr)) {
dp[i + 1] = Math.min(dp[i + 1], dp[j]);
}
}
}
return dp[n];
}
}
----------------------------------------------------------
--
https://i.imgur.com/DANRJFR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693661068.A.CA7.html