楼主:
Rushia (みけねこ的鼻屎)
2023-09-02 21:24:25https://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: