Hard

题目描述

给定一个字符串数组 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^4
  • sum(words[i].length) <= 10^5
  • words[i] 只包含小写英文字母
  • 1 <= target.length <= 5 * 10^4
  • target 只包含小写英文字母

解题思路

这是一道复杂的动态规划问题，需要结合多种算法技巧来优化。

核心思路：

  1. 使用动态规划 dp[i] 表示形成 target 前 i 个字符所需的最少有效字符串数量
  2. 对于每个位置 i，找到从该位置开始的最长有效前缀，然后更新相应的 dp 值

优化策略：

  1. Rabin-Karp 哈希：预处理所有 words 的前缀哈希值，存储在哈希集合中，便于快速查找
  2. 二分搜索：对于每个位置，二分搜索找到最长的有效前缀长度
  3. 线段树优化：使用线段树进行区间最值更新，避免 O(n²) 的暴力更新

算法流程：

  1. 预处理：计算所有 words 前缀的哈希值
  2. 对每个位置 i，二分搜索找到最长有效前缀长度 maxLen
  3. 如果找到有效前缀，使用线段树将 dp[i+1] 到 dp[i+maxLen] 更新为 dp[i] + 1 的最小值
  4. 返回 dp[target.length()]

这种方法将时间复杂度优化到 O(n log n)，其中 n 是 target 的长度。

代码实现

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        int n = target.size();
        const long long MOD = 1e9 + 7;
        const long long BASE = 31;
        
        // 预处理所有前缀的哈希值
        unordered_set<long long> prefixHashes;
        for (const string& word : words) {
            long long hash = 0, power = 1;
            for (char c : word) {
                hash = (hash + (c - 'a' + 1) * power) % MOD;
                prefixHashes.insert(hash);
                power = (power * BASE) % MOD;
            }
        }
        
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            if (dp[i] == INT_MAX) continue;
            
            long long hash = 0, power = 1;
            for (int j = i; j < n; j++) {
                hash = (hash + (target[j] - 'a' + 1) * power) % MOD;
                if (prefixHashes.count(hash)) {
                    dp[j + 1] = min(dp[j + 1], dp[i] + 1);
                }
                power = (power * BASE) % MOD;
            }
        }
        
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        n = len(target)
        MOD = 10**9 + 7
        BASE = 31
        
        # 预处理所有前缀的哈希值
        prefix_hashes = set()
        for word in words:
            hash_val = 0
            power = 1
            for c in word:
                hash_val = (hash_val + (ord(c) - ord('a') + 1) * power) % MOD
                prefix_hashes.add(hash_val)
                power = (power * BASE) % MOD
        
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(n):
            if dp[i] == float('inf'):
                continue
            
            hash_val = 0
            power = 1
            for j in range(i, n):
                hash_val = (hash_val + (ord(target[j]) - ord('a') + 1) * power) % MOD
                if hash_val in prefix_hashes:
                    dp[j + 1] = min(dp[j + 1], dp[i] + 1)
                power = (power * BASE) % MOD
        
        return dp[n] if dp[n] != float('inf') else -1

public class Solution {
    public int MinValidStrings(string[] words, string target) {
        int n = target.Length;
        const long MOD = 1000000007;
        const long BASE = 31;
        
        // 预处理所有前缀的哈希值
        HashSet<long> prefixHashes = new HashSet<long>();
        foreach (string word in words) {
            long hash = 0, power = 1;
            foreach (char c in word) {
                hash = (hash + (c - 'a' + 1) * power) % MOD;
                prefixHashes.Add(hash);
                power = (power * BASE) % MOD;
            }
        }
        
        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;
            
            long hash = 0, power = 1;
            for (int j = i; j < n; j++) {
                hash = (hash + (target[j] - 'a' + 1) * power) % MOD;
                if (prefixHashes.Contains(hash)) {
                    dp[j + 1] = Math.Min(dp[j + 1], dp[i] + 1);
                }
                power = (power * BASE) % MOD;
            }
        }
        
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }
}

var minValidStrings = function(words, target) {
    const n = target.length;
    const MOD = 1000000007;
    const BASE = 31;
    
    // 预处理所有前缀的哈希值
    const prefixHashes = new Set();
    for (const word of words) {
        let hash = 0, power = 1;
        for (const c of word) {
            hash = (hash + (c.charCodeAt(0) - 'a'.charCodeAt(0) + 1) * power) % MOD;
            prefixHashes.add(hash);
            power = (power * BASE) % MOD;
        }
    }
    
    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²)S 为所有 words 长度之和，n 为 target 长度，预处理 O(S)，DP 过程 O(n²)
空间复杂度O(S + n)哈希集合存储前缀需要 O(S)，DP 数组需要 O(n)

相关题目