2025-04-23：形成目标字符串需要的最少字符串数Ⅱ。用go语言，给定一个字符串数组 words 和一个目标字符串 target。

如果某个字符串 x 是数组 words 中任意字符串的前缀，则称 x 是一个有效字符串。

现在希望通过拼接若干个有效字符串，组成目标字符串 target。请计算完成这个拼接所需的最少字符串数量，若无法拼接出 target，则返回 -1。

1 <= words.length <= 100。

1 <= words[i].length <= 5 * 10000。

输入确保 sum(words[i].length) <= 100000。

words[i] 只包含小写英文字母。

1 <= target.length <= 5 * 10000。

target 只包含小写英文字母。

输入： words = [“abc”,“aaaaa”,“bcdef”], target = “aabcdabc”。

输出： 3。

解释：

target 字符串可以通过连接以下有效字符串形成：

words[1] 的长度为 2 的前缀，即 “aa”。

words[2] 的长度为 3 的前缀，即 “bcd”。

words[0] 的长度为 3 的前缀，即 “abc”。

题目来自leetcode3292。

解决思路

1. 预处理阶段：

   • 对于目标字符串 target 的每一个位置 i，我们需要知道从 words 中所有字符串的前缀中，能够覆盖 target 的前 i 个字符的最长前缀长度。这可以通过 KMP 算法的前缀函数（prefix function）来实现。
   • 具体来说，对于 words 中的每一个字符串 word，我们计算 word + "#" + target 的前缀函数数组 pi。这样，pi 数组的后半部分（即 target 的部分）会告诉我们 word 的前缀与 target 的各个子串的最长匹配长度。
   • 对于 target 的每一个位置 i，我们记录所有 words 中字符串的前缀能够覆盖 target 前 i 个字符的最长长度 back[i]。

2. 动态规划阶段：

   • 我们使用动态规划数组 dp，其中 dp[i] 表示构造 target 的前 i 个字符所需的最少有效字符串数量。
   • 初始化时，dp[0] = 0（空字符串不需要任何有效字符串），其余 dp[i] 初始化为一个很大的值（表示不可达）。
   • 对于 target 的每一个位置 i，我们利用预处理阶段得到的 back[i] 来更新 dp[i + 1]。具体来说，dp[i + 1] = min(dp[i + 1], dp[i + 1 - back[i]] + 1)。
   • 如果在动态规划过程中发现某个 dp[i] 的值超过了 target 的长度，说明无法构造 target，直接返回 -1。

3. 结果提取：

   • 最终 dp[n] 的值就是构造 target 所需的最少有效字符串数量。如果 dp[n] 仍然是初始化的很大值，说明无法构造 target，返回 -1。

具体步骤

1. 计算 back 数组：

   • 对于 words 中的每一个字符串 word，计算 word + "#" + target 的前缀函数 pi。
   • 对于 target 的每一个位置 i，back[i] 是所有 words 中字符串的前缀函数在 target 部分（即 pi[m + 1 + i]，其中 m 是 word 的长度）的最大值。

2. 动态规划填充 dp 数组：

   • 初始化 dp[0] = 0，其余 dp[i] = ∞。
   • 对于 i 从 0 到 n - 1：
     • 如果 back[i] == 0，说明无法从 words 中找到一个前缀覆盖 target 的前 i + 1 个字符，跳过。
     • 否则，dp[i + 1] = min(dp[i + 1], dp[i + 1 - back[i]] + 1)。
     • 如果 dp[i + 1] > n，直接返回 -1。

3. 返回结果：

   • 如果 dp[n] 仍然是 ∞，返回 -1；否则返回 dp[n]。

时间复杂度和空间复杂度

• 时间复杂度：
  • 预处理阶段：对于每一个 word，计算 word + "#" + target 的前缀函数的时间复杂度为 O(m + n)，其中 m 是 word 的长度，n 是 target 的长度。由于 sum(words[i].length) <= 100000，预处理阶段的总时间复杂度为 O(sum(m) + k * n)，其中 k 是 words 的数量。由于 k <= 100，可以简化为 O(sum(m) + n)。
  • 动态规划阶段：填充 dp 数组的时间复杂度为 O(n)。
  • 总时间复杂度：O(sum(m) + n)。
• 空间复杂度：
  • back 数组：O(n)。
  • dp 数组：O(n)。
  • 前缀函数 pi：O(m + n)（临时空间，可以复用）。
  • 总空间复杂度：O(n + m)（其中 m 是最大的 word 长度）。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minValidStrings(words []string, target string) int {
	prefixFunction := func(word, target string) []int {
		s := word + "#" + target
		n := len(s)
		pi := make([]int, n)
		for i := 1; i < n; i++ {
			j := pi[i-1]
			for j > 0 && s[i] != s[j] {
				j = pi[j-1]
			}
			if s[i] == s[j] {
				j++
			}
			pi[i] = j
		}
		return pi
	}

	n := len(target)
	back := make([]int, n)
	for _, word := range words {
		pi := prefixFunction(word, target)
		m := len(word)
		for i := 0; i < n; i++ {
			back[i] = int(math.Max(float64(back[i]), float64(pi[m+1+i])))
		}
	}

	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = int(1e9)
	}
	for i := 0; i < n; i++ {
		dp[i+1] = dp[i+1-back[i]] + 1
		if dp[i+1] > n {
			return -1
		}
	}
	return dp[n]
}

func main() {
	words := []string{"abc", "aaaaa", "bcdef"}
	target := "aabcdabc"
	results := minValidStrings(words, target)
	fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minValidStrings(words, target):
    n = len(target)
    if n == 0:
        return 0

    def prefix_function(word, target_str):
        s = word + '#' + target_str
        pi = [0] * len(s)
        for i in range(1, len(s)):
            j = pi[i-1]
            while j > 0 and s[i] != s[j]:
                j = pi[j-1]
            if s[i] == s[j]:
                j += 1
            pi[i] = j
        return pi

    back = [0] * n
    for word in words:
        m = len(word)
        if m == 0:
            continue
        pi = prefix_function(word, target)
        for i in range(n):
            pos = m + 1 + i
            current_pi = pi[pos] if pos < len(pi) else 0
            if current_pi > back[i]:
                back[i] = current_pi

    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(n):
        k = back[i]
        prev = (i + 1) - k
        if prev < 0:
            return -1
        if dp[prev] + 1 < dp[i+1]:
            dp[i+1] = dp[prev] + 1
        if dp[i+1] > n:
            return -1

    return dp[n] if dp[n] != float('inf') else -1

# 示例测试
if __name__ == "__main__":
    words = ["abc", "aaaaa", "bcdef"]
    target = "aabcdabc"
    print(minValidStrings(words, target))