本文涉及知识点

C++动态规划

LeetCode2707. 字符串中的额外字符

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s ，使剩下的字符 最少 。
示例 1：
输入：s = “leetscode”, 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 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] 和 s 只包含小写英文字母。
dictionary 中的单词互不相同。

动态规划

通过i,j枚举子数组：can[i][j] 表示s[i…j]是否在字典中存在。时间复杂度：O(nnn)。

动态规划的状态表示

dp[i]表示nums的前i个元素的最少额外字符。空间复杂度：O(n)

动态规划的填表顺序

枚举前置状态 i = 0 to n-1 j = i To n-1

动态规划的状态表示

MinSelf(dp[i+1],dp[i]+1)
如果can[i][j]成立，则MinSelf(dp[j+1],dp[i])。
单个状态转移的时间复杂度是O(n），总时间复杂度是O(nn)。

动态规划的初始值

dp[0]=0

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int minExtraChar(string s, vector<string>& dictionary) {
				const int N = s.length();
				unordered_set<string> sset(dictionary.begin(), dictionary.end());	
				vector<vector<bool>> can(N, vector<bool>(N));
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						can[i][j] = sset.count(s.substr(i, j - i + 1));
					}
				}
				vector<int> dp(N + 1, INT_MAX / 2);
				dp[0] = 0;
				for (int i = 0; i  < N; i++) {
					dp[i + 1] = min(dp[i + 1], dp[i] + 1);
					for (int j = i; j < N; j++) {
						if (can[i][j]) dp[j + 1] = min(dp[j + 1], dp[i]);
					}
				}
				return dp.back();
			}
		};

单元测试

string s;
		vector<string> dictionary;
		TEST_METHOD(TestMethod11)
		{
			s = "leetscode", dictionary = { "leet", "code", "leetcode" };
			auto res = Solution().minExtraChar(s, dictionary);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "sayhelloworld", dictionary = {"hello", "world"	};
			auto res = Solution().minExtraChar(s, dictionary);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "dwmodizxvvbosxxw", dictionary = { "ox","lb","diz","gu","v","ksv","o","nuq","r","txhe","e","wmo","cehy","tskz","ds","kzbu" };
			auto res = Solution().minExtraChar(s, dictionary);
			AssertEx(7, res);
		}