本文涉及知识点

C++动态规划
C++前缀树(字典树)

LeetCode3291. 形成目标字符串需要的最少字符串数 I

给你一个字符串数组 words 和一个字符串 target。
如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例 1：
输入： words = [“abc”,“aaaaa”,“bcdef”], target = “aabcdabc”
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1] 的长度为 2 的前缀，即 “aa”。
words[2] 的长度为 3 的前缀，即 “bcd”。
words[0] 的长度为 3 的前缀，即 “abc”。
示例 2：
输入： words = [“abababab”,“ab”], target = “ababaababa”
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0] 的长度为 5 的前缀，即 “ababa”。
words[0] 的长度为 5 的前缀，即 “ababa”。
示例 3：
输入： words = [“abcdef”], target = “xyz”
输出： -1
提示：
1 <= words.length <= 100
1 <= words[i].length <= 5 * 10³
输入确保 sum(words[i].length) <= 10⁵。
words[i] 只包含小写英文字母。
1 <= target.length <= 5 * 10³
target 只包含小写英文字母。

字典树+划分型动态规划

m=words的字符数量，n = target.length。将所有wrod[i]放到字典树tree中。如果x在tree中存在，则是合法前缀。空间复杂度：O(26m)。 26是小写字母的数量。

动态规划的状态表示

dp[i]表示target前i个字符已经划分完的最少字符数。

动态规划的填报顺序

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

动态规划的转移方程

查询nums[i…j-1]的基础上查询nums[i…j]是否是合法前缀的时间复杂度是：O(1)。如果nums[i…j]合法：MinSelf(dp[j+1],dp[i]+1)
时间复杂度：O(nn)

动态规划的初始值

dp[0]=0，其它是INT_MAX/2。

动态规划的返回值

dp.back() 如果>=INT_MAX/2，返回-1。

代码

核心代码

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:
	~CTrieNode()
	{
		for (auto& [tmp, ptr] : m_dataToChilds) {
			delete ptr;
		}
	}
	CTrieNode* AddChar(TData ele, int& iMaxID)
	{
#ifdef _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		const int index = ele - cBegin;
		auto ptr = m_dataToChilds[ele - cBegin];
		if (!ptr)
		{
			m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUG
			m_dataToChilds[index]->m_iID = ++iMaxID;
			m_childForDebug[ele] = m_dataToChilds[index];
#endif
		}
		return m_dataToChilds[index];
	}
	CTrieNode* GetChild(TData ele)
	{
#ifdef _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		return m_dataToChilds[ele - cBegin];
	}
protected:
#ifdef _DEBUG
	int m_iID = -1;
	std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:
	int m_iLeafIndex = -1;
protected:
	//CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节
	//unordered_map<int, CTrieNode*>    m_dataToChilds;//时间换空间 大约56字节
	map<int, CTrieNode*>    m_dataToChilds;//时间换空间,空间略优于哈希映射，数量小于256时，时间也优。大约48字节
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:
	int GetLeadCount()
	{
		return m_iLeafCount;
	}
	CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue)
	{
		auto curNode =par->AddChar(curValue, m_iMaxID);
		FreshLeafIndex(curNode);
		return curNode;
	}
	template<class IT>
	int Add(IT begin, IT end)
	{
		auto pNode = &m_root;
		for (; begin != end; ++begin)
		{
			pNode = pNode->AddChar(*begin, m_iMaxID);
		}
		FreshLeafIndex(pNode);
		return pNode->m_iLeafIndex;
	}	
	template<class IT>
	CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end)
	{
		auto ptr = &m_root;
		for (; begin != end; ++begin)
		{
			ptr = ptr->GetChild(*begin);
			if (nullptr == ptr)
			{
				return nullptr;
			}
		}
		return ptr;
	}
	CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:
	void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode)
	{
		if (-1 == pNode->m_iLeafIndex)
		{
			pNode->m_iLeafIndex = m_iLeafCount++;
		}
	}
	int m_iMaxID = 0;
	int m_iLeafCount = 0;
};
class Solution {
		public:
			int minValidStrings(vector<string>& words, string target) {
				CTrie<> trie;
				for (const auto& s : words) {
					trie.Add(s.begin(), s.end());
				}
				const int N = target.length();
				vector<int> dp(N + 1, INT_MAX / 2);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					auto ptr = &trie.m_root;
					if (dp[i] >= INT_MAX / 2) { continue; }
					for (int j = i; j < N; j++) {
						ptr = ptr->GetChild(target[j]);
						if (nullptr == ptr) { break; }
						dp[j + 1] = min(dp[j + 1], dp[i] + 1);
					}
				}
				const auto ans = dp.back();
				return (ans >= INT_MAX / 2) ? -1 : ans;
			}
		};

单元测试

	vector<string> words;
		string target;
		TEST_METHOD(TestMethod11)
		{
			words = { "abc", "aaaaa", "bcdef" }, target = "aabcdabc";
			auto res = Solution().minValidStrings(words, target);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			words = { "abababab", "ab" }, target = "ababaababa";
			auto res = Solution().minValidStrings(words, target);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			words = { "abcdef" }, target = "def";
			auto res = Solution().minValidStrings(words, target);
			AssertEx(-1, res);
		}