Medium

题目描述

给定一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中任意字符串的前缀，则称 x 为有效字符串。

返回能够连接形成 target 的最少有效字符串数目。如果无法形成 target，返回 -1。

示例 1：

输入：words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
输出：3
解释：
目标字符串可以通过连接以下字符串形成：
- words[1] 的长度为 2 的前缀，即 "aa"。
- words[2] 的长度为 3 的前缀，即 "bcd"。
- words[0] 的长度为 3 的前缀，即 "abc"。

示例 2：

输入：words = ["abababab","ab"], target = "ababaababa"
输出：2
解释：
目标字符串可以通过连接以下字符串形成：
- 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 仅包含小写英文字母

解题思路

这道题是一个经典的动态规划问题，需要找到用最少的有效字符串拼接成目标字符串的方法。

核心思路：

  1. 使用前缀树（Trie）来高效存储和查找所有 words 中字符串的前缀
  2. 定义 dp[i] 表示形成 target 前 i 个字符所需的最少有效字符串数目
  3. 状态转移：对于每个位置 i，尝试从位置 i 开始的所有可能前缀匹配

算法步骤：

  1. 构建前缀树，将所有 words 中的字符串插入
  2. 初始化 dp 数组，dp[0] = 0，其余为无穷大
  3. 对于每个位置 i (0 ≤ i < target.length)：
    • 如果 dp[i] 为无穷大，跳过（无法到达此位置）
    • 从位置 i 开始，在前缀树中尝试匹配尽可能长的前缀
    • 对于每个匹配的前缀长度 len，更新 dp[i + len] = min(dp[i + len], dp[i] + 1)

这种方法的优势是通过前缀树避免了重复的字符串匹配，时间复杂度较优。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    void insert(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
    }
    
    int minValidStrings(vector<string>& words, string target) {
        TrieNode* root = new TrieNode();
        
        // 构建前缀树
        for (const string& word : words) {
            insert(root, word);
        }
        
        int n = target.length();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            if (dp[i] == INT_MAX) continue;
            
            TrieNode* node = root;
            for (int j = i; j < n; j++) {
                int idx = target[j] - 'a';
                if (!node->children[idx]) break;
                node = node->children[idx];
                dp[j + 1] = min(dp[j + 1], dp[i] + 1);
            }
        }
        
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        class TrieNode:
            def __init__(self):
                self.children = {}
        
        root = TrieNode()
        
        # 构建前缀树
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
        
        n = len(target)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(n):
            if dp[i] == float('inf'):
                continue
            
            node = root
            for j in range(i, n):
                if target[j] not in node.children:
                    break
                node = node.children[target[j]]
                dp[j + 1] = min(dp[j + 1], dp[i] + 1)
        
        return dp[n] if dp[n] != float('inf') else -1

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[26];
    }
    
    private void Insert(TrieNode root, string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int idx = c - 'a';
            if (node.Children[idx] == null) {
                node.Children[idx] = new TrieNode();
            }
            node = node.Children[idx];
        }
    }
    
    public int MinValidStrings(string[] words, string target) {
        TrieNode root = new TrieNode();
        
        // 构建前缀树
        foreach (string word in words) {
            Insert(root, word);
        }
        
        int n = target.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            if (dp[i] == int.MaxValue) continue;
            
            TrieNode node = root;
            for (int j = i; j < n; j++) {
                int idx = target[j] - 'a';
                if (node.Children[idx] == null) break;
                node = node.Children[idx];
                dp[j + 1] = Math.Min(dp[j + 1], dp[i] + 1);
            }
        }
        
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }
}

var minValidStrings = function(words, target) {
    class TrieNode {
        constructor() {
            this.children = {};
        }
    }
    
    const root = new TrieNode();
    
    // 构建前缀树
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
    }
    
    const n = target.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 0; i < n; i++) {
        if (dp[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(S + N × M)，其中 S 是所有 words 字符串的总长度，N 是 target 的长度，M 是最长匹配前缀的长度
空间复杂度O(S + N)，前缀树占用 O(S) 空间，dp 数组占用 O(N) 空间

相关题目