补题 力扣双周赛105 [LeetCode6394] 字符串中的额外字符

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符 最少 。

示例 1：

1
2
3
输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
输出：1
解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。

示例 2：

1
2
3
输入：s = "sayhelloworld", dictionary = ["hello","world"]
输出：3
解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。

题解

题目解析

又又又是一道dp题…可是我又又又没看出来…

这个题目的状态转移方程并不是十分好想,但是仔细想一下貌似也能理解:

1
2
3
4
这里的dp[i]都要注意,因为这个是代表的前i-1个的最少字符数.
dp[i]第i个字母前面i-1个字母中的单独的最少字符数.
dp[i-1]+1为第i-1个字母不选.
dp[k]为选了其中匹配的一个字典里的词,然后剩下的前面一部分的最小值加上去,前一部分的长度为k-1.

从他们写的代码中学到许多STL中的新函数和新用法,这些东西会放到Remark部分中.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <cstring>
#include <algorithm>
#define endl "\n"
using namespace std;

int main(string s, vector<string>& dictionary){
	unordered_set<string> st(dictionary.begin(),dictionary.end());
	vector<int> dp(s.size()+10,0);
	for(int i=1;i<=s.size();i++){
		dp[i] = dp[i-1] + 1;
		for(int j=0;j<i;j++){
			//(j,i-j)分割的字串为[j,i)<=>[j,i-1]
			if(st.count(s.substr(j,i-j)))
				dp[i] = min(dp[j],dp[i]);
		}
	}
	return dp[s.size()];
}

Remark

  • unordered_set 新数据类型,无序集合.据说是找东西比较快,是Hash表搞的.
  • string.substr(s.begin(),length) 截取 [s.begin(),s.begin()+length) 范围的字串并作为返回值.