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

福大大架构师每日一题

发布于 2025-04-23 09:35:45

5400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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-*-

defminValidStrings(words, target):
    n = len(target)
    if n == 0:
        return0

    defprefix_function(word, target_str):
        s = word + '#' + target_str
        pi = [0] * len(s)
        for i inrange(1, len(s)):
            j = pi[i-1]
            while j > 0and 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 inrange(n):
            pos = m + 1 + i
            current_pi = pi[pos] if pos < len(pi) else0
            if current_pi > back[i]:
                back[i] = current_pi

    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i inrange(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))