Leetcode打卡:形成目标字符串需要的最少字符串数II

embedded/2024/12/20 0:06:26/

执行结果:通过

题目:3292  形成目标字符串需要的最少字符串数II

给你一个字符串数组 words 和一个字符串 target

如果字符串 x 是 words 中 任意 字符串的 

前缀

,则认为 x 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 target ,请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target,则返回 -1

示例 1:

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

输出: 3

解释:

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

  • words[1] 的长度为 2 的前缀,即 "aa"
  • words[2] 的长度为 3 的前缀,即 "bcd"
  • words[0] 的长度为 3 的前缀,即 "abc"

示例 2:

输入: words = ["abababab","ab"], target = "ababaababa"

输出: 2

解释:

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

  • words[0] 的长度为 5 的前缀,即 "ababa"
  • words[0] 的长度为 5 的前缀,即 "ababa"

示例 3:

输入: words = ["abcdef"], target = "xyz"

输出: -1

提示:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 5 * 104
  • 输入确保 sum(words[i].length) <= 105.
  • words[i]  只包含小写英文字母。
  • 1 <= target.length <= 5 * 104
  • target  只包含小写英文字母。

代码以及解题思路

代码

class Solution:def minValidStrings(self, words: List[str], target: str) -> int:n = reduce(lambda a, b: a + len(b), words, 1)ac = AC(n)for i, word in enumerate(words):ac.insert(word, 1)ac.build()ans = ac.search(target)return ans
class AC:def __init__(self, N: int):self.tot = 0self.tr = [[0] * 26 for _ in range(N)]self.e = [0] * N self.cost = [1] * Nself.len = [0] * Nself.fail = [0] * Nself.last = [0] * Ndef insert(self, word: str, cost: int) -> None:u = 0for i, ch in enumerate(word):ch = ord(ch) - ord("a")if self.tr[u][ch] == 0:self.tot += 1self.tr[u][ch] = self.totu = self.tr[u][ch]self.len[u] = i + 1self.e[u] += 1def build(self) -> None:dq = deque()for i in range(26):if self.tr[0][i] != 0:dq.append(self.tr[0][i])while dq:u = dq.popleft()for i in range(26):if self.tr[u][i] != 0:self.fail[self.tr[u][i]] = self.tr[self.fail[u]][i]self.last[self.tr[u][i]] = self.fail[self.tr[u][i]] if self.len[self.fail[self.tr[u][i]]] else self.last[self.fail[self.tr[u][i]]]dq.append(self.tr[u][i])else:self.tr[u][i] = self.tr[self.fail[u]][i]def search(self, word: str) -> int:n = len(word)dp = [0] * (n+1)u = 0for i in range(1, n+1):ch = ord(word[i-1]) - ord("a")u = self.tr[u][ch]if u == 0:return -1dp[i] = dp[i - self.len[u]] + 1return dp[n]

解题思路:

  1. 初始化 AC 自动机
    • AC 自动机是一种用于多模式字符串匹配的数据结构,可以看作是一个Trie(前缀树)与KMP(Knuth-Morris-Pratt)算法的结合。
    • 初始化时,需要构建一个Trie树,并添加失败指针(fail指针),使得在匹配失败时可以跳转到另一个状态继续匹配。
  2. 构建 AC 自动机
    • 将所有单词插入到Trie树中,并记录每个节点的信息,如节点对应的字符串长度、是否是某个单词的结尾等。
    • 使用广度优先搜索(BFS)构建失败指针,使得每个节点在匹配失败时可以跳转到另一个节点继续匹配。
  3. 动态规划求解最小有效字符串数量
    • 使用动态规划数组 dp,其中 dp[i] 表示形成 target 的前 i 个字符所需的最小有效字符串数量。
    • 遍历 target 的每个字符,利用AC自动机在Trie树中查找当前字符可能匹配的最长前缀。
    • 更新 dp[i] 为 dp[i - len(匹配的前缀)] + 1,表示通过添加一个有效字符串(包含当前匹配的前缀)来形成 target 的前 i 个字符。
    • 如果在某个位置无法匹配任何前缀(即AC自动机的当前状态为0),则无法形成 target,返回 -1。
  4. 返回结果
    • 遍历完成后,dp[n]n 是 target 的长度)即为形成整个 target 所需的最小有效字符串数量。

代码细节

  • reduce(lambda a, b: a + len(b), words, 1):计算所有单词的总长度,用于初始化AC自动机的大小。
  • AC 类:实现了AC自动机的构建和搜索功能。
    • insert 方法:将单词插入Trie树。
    • build 方法:构建失败指针。
    • search 方法:使用动态规划搜索形成 target 的最小有效字符串数量。

注意事项


http://www.ppmy.cn/embedded/147141.html

相关文章

环境变革下 B2B 销售的转型与创新:开源 AI 智能名片与 S2B2C 商城小程序的助力

摘要&#xff1a;本文探讨了在信息科技与互联网迅猛发展所引发的环境改变背景下&#xff0c;B2B 销售工作面临的挑战与机遇。深入分析了传统销售模式的局限性以及新环境对销售人员素质和能力的要求&#xff0c;提出从提供“信息”向提供“业务价值”转变的必要性。同时&#xf…

python学opencv|读取图像(十三)BGR图像和HSV图像互相转换深入

【1】引言 前序学习过程中&#xff0c;我们偶然发现&#xff1a;如果原始图像是png格式&#xff0c;将其从BGR转向HSV&#xff0c;再从HSV转回BGR后&#xff0c;图像的效果要好于JPG格式。 文章链接为&#xff1a; python学opencv|读取图像&#xff08;十二&#xff09;BGR图…

车载通信架构 --- 一个以太网帧包含多个DoIP帧?

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所谓鸡汤,要么蛊惑你认命,要么怂恿你拼命,但都是回避问题的根源,以现象替代逻辑,以情绪代替思考,把消极接受现实的懦弱,伪装成乐观面对不幸的…

k8s kubernetes

文章目录 CGroupk8s运行时k8s组件k8s组件安装kubeadm命令kubectl命令k8s官网代码 CGroup 在 Linux 上&#xff0c;控制组&#xff08;CGroup&#xff09;用于限制分配给进程的资源。kubelet 和底层容器运行时都需要对接控制组来强制执行 为 Pod 和容器管理资源 并为诸如 CPU、…

小程序子组件调用父组件方法、父组件调用子组件方法

1、子组件调用父组件方法 子组件this.triggerEvent(finish); startShare(e) {let url config.apiUrl "/business/lzShare/edit";let data this.data.currentData;util.httpPut(url, data).then((res) > {this.triggerEvent(finish);console.log(res.result);})…

pyparsing restOfLine

在 pyparsing 中&#xff0c;restOfLine 是一个解析器&#xff08;parser&#xff09;&#xff0c;用于匹配当前位置到行尾的所有内容&#xff0c;通常在解析文件或处理逐行数据时非常有用。 restOfLine 的特性 匹配内容&#xff1a;从当前位置一直匹配到换行符 \n 或字符串结…

StarRocks:存算一体模式部署

目录 一、StarRocks 简介 二、StarRocks 架构 2.1 存算一体 2.2 存算分离 三、前期准备 3.1前提条件 3.2 集群规划 3.3 配置环境 3.4 准备部署文件 四、手动部署 4.1 部署FE节点 4.2 部署BE节点 4.3 部署CN节点&#xff08;可选&#xff09; 4.4 FE高可用…

OpenAI 正式赋予 ChatGPT 通过视频实时与用户互动的能力

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…