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

福大大架构师每日一题

发布于 2025-04-22 10:18:43

13600

代码可运行

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

运行总次数：0

代码可运行

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

如果一个字符串 x 是 words 中某个字符串的开头部分（前缀），那么它被视为有效字符串。

现在希望通过拼接这些有效字符串来组装出 target，求出拼接所需的最少字符串数量。如果无法拼出 target，则返回 -1。

1 <= words.length <= 100。

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

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

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

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

target 只包含小写英文字母。

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

输出： 3。

解释：

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

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

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

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

题目来自leetcode3291。

算法流程分解

1. 构建“最长公共前缀数组”（KMP 算法的 prefix function）

• 对于每个words中的字符串word，和目标字符串target，我们用 KMP 算法计算字符串：word + "#" + target的 prefix function 数组pi。
• 这个 prefix function 数组pi记录的是：
- • 以当前索引结尾的字符串s，其最长的相同前缀长度有多长。
• 这里word + "#" + target这样拼接是为了避免word后缀与target前缀的错误匹配，从而准确找到target中各个位置与word前缀的最长匹配长度。

2. 计算 target 中每个位置可以匹配的最长有效字符串长度

• 定义数组back，长度等于target的长度。
• 对每个word，利用对应的前缀匹配数组pi，更新back中相应位置的值。
• 具体来说：
- • 在pi中，m = len(word), 从索引m + 1开始是target的匹配信息。
- • 对target的第i个字符，back[i] = max(back[i], pi[m + 1 + i])。
- • 这个back[i]表示从target[i]位置开始，可以匹配到的最大有效字符串的长度。
• 举例：
- • 如果back[0] = 2，说明从target开头起，可以匹配某个word的长度为2的前缀，是一个有效字符串。

3. 利用动态规划计算最少拼接字符串数

• 定义动态规划数组dp，长度为len(target) + 1，它表示拼接到target中索引为i（前缀长度为i）所需的最少有效字符串数量。
• 初始化：
- •dp[0] = 0，拼接空字符串需要0个字符串。
- • 其余位置初始化为一个较大的数，表示尚未计算或不可达。
• 状态转移：
- • 对i从 0 到len(target)-1遍历：
  - • 利用back[i]，代表从位置i开始能匹配的最大有效字符串长度length = back[i]。
  - • 同时更新dp[i + length] = min(dp[i + length], dp[i] + 1)，表示使用一个有效字符串拼接该段后，拼接到位置i + length所需的最少字符串数量。
• 如果最后dp[len(target)]的值依旧是未修改的无穷大，说明无法拼出target，返回 -1。
• 否则返回最小值。

复杂度分析

时间复杂度

• 假设：
- •W是words数组中所有字符串长度的总和，W = sum(len(words[i]))，题目限制W <= 100000。
- •N = len(target)，N <= 5000。
• 对每个word：
- • 计算 prefix function 时间为O(len(word) + N)。
• 总时间为：
- • 所有 word 前缀函数计算的时间和，即O(W + N * len(words))。
- • 这里因为len(words) <= 100，且N <= 5000，整体为O(W + N * 100)在最大输入下仍可接受。
• 动态规划部分为O(N)。
•总结时间复杂度： O(W + N * len(words))，其中最关键是 prefix function 计算。

空间复杂度

• 主要空间开销：
- • 存储 prefix function 数组：最大长度为len(word) + 1 + N，每次计算占用O(len(word) + N)，临时空间。
- • 动态规划数组dp：长度为N+1，空间为O(N)。
- • 辅助数组back：长度为N，空间为O(N)。
• 由于 prefix function 每次计算后数组可释放，所以额外空间主要为O(N + max(len(word)))。

总结

• 算法核心利用了 KMP 算法的 prefix function 来高效求每个位置能匹配的最大有效字符串长度，避免暴力匹配。
• 通过动态规划计算拼接所需的最小字符串数。
• 适合处理中等长度目标字符串和大量中长字符串的组合问题。
• 时间复杂度主要受 prefix function 计算影响，空间复杂度较低，符合题目给定限制。

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
    back = [0] * n

    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

    for word in words:
        m = len(word)
        pi = prefix_function(word, target)
        for i inrange(n):
            index_in_pi = m + 1 + i
            if index_in_pi < len(pi):
                back[i] = max(back[i], pi[index_in_pi])

    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i inrange(n):
        l = back[i]
        prev_pos = (i + 1) - l
        if prev_pos >= 0:
            if dp[prev_pos] + 1 < dp[i + 1]:
                dp[i + 1] = dp[prev_pos] + 1

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

# Example usage:
words = ["abc", "aaaaa", "bcdef"]
target = "aabcdabc"
print(minValidStrings(words, target))  # Output: 3