用 C++ 完成以下任務 You are given an array of strings words and a string target. A string x is…
- User
用 C++ 完成以下任務 You are given an array of strings words and a string target.
A string x is called valid if x is a prefix of any string in words.
Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
Example 1:
Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
Output: 3
Explanation:
The target string can be formed by concatenating:
Prefix of length 2 of words[1], i.e. "aa". Prefix of length 3 of words[2], i.e. "bcd". Prefix of length 3 of words[0], i.e. "abc". Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
Prefix of length 5 of words[0], i.e. "ababa". Prefix of length 5 of words[0], i.e. "ababa". Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 100 1 <= words[i].length <= 5 * 104 The input is generated such that sum(words[i].length) <= 105. words[i] consists only of lowercase English letters. 1 <= target.length <= 5 * 104 target consists only of lowercase English letters. 實做 function 為 class Solution { public: int minValidStrings(vector& words, string target) {
}};
- Assistant
要解决这个问题,我们需要找到最小数量的有效字符串(即任何
words中字符串的前缀)来拼接成目标字符串target。算法思路:
-
构建Trie树(前缀树):
- 我们将
words中的所有字符串的所有前缀插入到 Trie 树中。 - 每个节点都代表一个前缀,由于任何前缀都是有效的,所以所有节点都是接受状态。
- 我们将
-
使用广度优先搜索(BFS):
- 我们从目标字符串的起始位置0开始,用队列来存储待处理的位置。
- 对于每个位置,我们尝试尽可能匹配 Trie 树中的路径。
- 每当我们在 Trie 树中前进一步时,如果我们到达了新的位置并且之前没有到达过,我们将该位置加入队列。
- 我们在遍历时记录步数,即拼接的字符串数量。
-
避免重复处理:
- 我们使用一个
visited数组来记录已经访问过的位置,防止重复处理,从而优化性能。
- 我们使用一个
时间复杂度分析:
- 构建 Trie 树的时间复杂度是 O(total_length_of_words),其中 total_length_of_words 是所有
words中字符串长度的总和。 - BFS 遍历的时间复杂度近似为 O(n),其中 n 为目标字符串
target的长度,因为每个位置在最坏情况下最多只会被访问一次。
代码实现:
#include <iostream> #include <vector> #include <queue> #include <unordered_map> using namespace std; class TrieNode { public: unordered_map<char, TrieNode*> children; // 因为每个节点都代表一个前缀,所以都是接受状态,不需要额外标记 }; class Solution { public: int minValidStrings(vector<string>& words, string target) { // 构建 Trie 树 TrieNode* root = new TrieNode(); for (const string& word : words) { TrieNode* node = root; for (char c : word) { if (!node->children.count(c)) { node->children[c] = new TrieNode(); } node = node->children[c]; } } int n = target.size(); vector<bool> visited(n + 1, false); queue<pair<int, int>> q; // pair(position, steps) q.push({0, 0}); visited[0] = true; while (!q.empty()) { auto [u, steps] = q.front(); q.pop(); TrieNode* node = root; for (int i = u; i < n; ++i) { char c = target[i]; if (!node->children.count(c)) { break; } node = node->children[c]; int next_pos = i + 1; if (!visited[next_pos]) { visited[next_pos] = true; if (next_pos == n) { return steps + 1; // 到达末尾,返回最小拼接数 } q.push({next_pos, steps + 1}); } } } // 无法拼接成目标字符串 return -1; } };测试用例验证:
您可以根据题目提供的示例测试用例进行验证,确保函数返回期望的结果。
总结:
通过构建 Trie 树和使用 BFS,我们能够高效地找到最小数量的有效字符串来拼接成目标字符串。在实现中,需要注意优化时间复杂度,避免冗余的计算。
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.