专门做家具网站,动画设计说明,wordpress用户id,wordpress百度云下载Powered by:NEFU AB-IN
Link 文章目录 3213. 最小代价构造字符串题意思路代码 3213. 最小代价构造字符串
题意
给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs#xff0c;这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数包括零次
选择一个在范围 [0, words.length - 1] 的索引 i。 将 words[i] 追加到 s。 该操作的成本是 costs[i]。 返回使 s 等于 target 的 最小 成本。如果不可能返回 -1。
思路
字典树/字符串哈希 dp
使用 Trie 树存储单词和成本 我们将所有的单词和对应的成本插入到一个 Trie 树中。Trie 树是一种多叉树可以快速查找以某个前缀开头的所有单词。 这样我们就能在 Trie 树中快速查找到以 target 中某个位置开始的所有前缀单词及其成本。动态规划Dynamic Programming 使用一个动态规划数组 dp其中 dp[i] 表示构造 target 的前 i 个字符的最小成本。 初始化 dp[0] 0表示构造空字符串的成本为 0其他位置初始化为无穷大表示尚未计算到该位置。遍历目标字符串 对于目标字符串 target 的每一个位置 i如果 dp[i] 是无穷大表示不能从当前位置开始构造则跳过。 否则使用 Trie 树的 search 方法从当前位置 i 开始查找所有可能的前缀及其成本。 对于每一个找到的前缀更新 dp 数组dp[i length] min(dp[i length], dp[i] cost)表示从当前位置 i 开始构造到 i length 的最小成本。
代码
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union# Constants
TYPE TypeVar(TYPE)
N int(2e5 10) # If using AR, modify accordingly
M int(20) # If using AR, modify accordingly
INF int(2e9)
OFFSET int(100)# Set recursion limit
setrecursionlimit(INF)class Arr:array staticmethod(lambda x0, sizeN: [x] * size)array2d staticmethod(lambda x0, rowsN, colsM: [Arr.array(x, cols) for _ in range(rows)])graph staticmethod(lambda sizeN: [[] for _ in range(size)])staticmethoddef to_1_indexed(data: Union[List, str, List[List]]):Adds a zero prefix to the data and returns the modified data and its length.if isinstance(data, list):if all(isinstance(item, list) for item in data): # Check if its a 2D arraynew_data [[0] * (len(data[0]) 1)] [[0] row for row in data]return new_data, len(new_data) - 1, len(new_data[0]) - 1else:new_data [0] datareturn new_data, len(new_data) - 1elif isinstance(data, str):new_data 0 datareturn new_data, len(new_data) - 1else:raise TypeError(Input must be a list, a 2D list, or a string)class Str:letter_to_num staticmethod(lambda x: ord(x.upper()) - 65) # A - 0num_to_letter staticmethod(lambda x: ascii_uppercase[x]) # 0 - Aremoveprefix staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)removesuffix staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)class Math:max staticmethod(lambda a, b: a if a b else b)min staticmethod(lambda a, b: a if a b else b)class IO:input staticmethod(lambda: stdin.readline().rstrip(\r\n))read staticmethod(lambda: map(int, IO.input().split()))read_list staticmethod(lambda: list(IO.read()))class Std:staticmethoddef find(container: Union[List[TYPE], str], value: TYPE):Returns the index of value in container or -1 if value is not found.if isinstance(container, list):try:return container.index(value)except ValueError:return -1elif isinstance(container, str):return container.find(value)staticmethoddef pairwise(iterable):Return successive overlapping pairs taken from the input iterable.a, b tee(iterable)next(b, None)return zip(a, b)staticmethoddef bisect_left(a, x, keylambda y: y):The insertion point is the first position where the element is not less than x.left, right 0, len(a)while left right:mid (left right) 1if key(a[mid]) x:left mid 1else:right midreturn leftstaticmethoddef bisect_right(a, x, keylambda y: y):The insertion point is the first position where the element is greater than x.left, right 0, len(a)while left right:mid (left right) 1if key(a[mid]) x:left mid 1else:right midreturn leftclass SparseTable:def __init__(self, data: list, funclambda x, y: x | y):Initialize the Sparse Table with the given data and function.self.func funcself.st [list(data)]i, n 1, len(self.st[0])while 2 * i n:pre self.st[-1]self.st.append([func(pre[j], pre[j i]) for j in range(n - 2 * i 1)])i 1def query(self, begin: int, end: int):Query the combined result over the interval [begin, end].lg (end - begin 1).bit_length() - 1return self.func(self.st[lg][begin], self.st[lg][end - (1 lg) 1])class TrieNode:def __init__(self):Initialize children dictionary and cost. The trie tree is a 26-ary tree.self.children {}self.cost INFdef add(self, word, cost):Add a word to the trie with the associated cost.node selffor c in word:if c not in node.children:node.children[c] Std.TrieNode()node node.children[c]node.cost min(node.cost, cost)def search(self, word):Search for prefixes of word in the trie and return their lengths and costs.node selfans []for i, c in enumerate(word):if c not in node.children:breaknode node.children[c]if node.cost ! INF:ans.append([i 1, node.cost]) # i 1 to denote length from startreturn ansclass StringHash:def __init__(self, s: str, mod: int 1_070_777_777):Initialize the StringHash object with the string, base, and mod.self.s sself.mod modself.base random.randint(8 * 10 ** 8, 9 * 10 ** 8)self.n len(s)self.pow_base [1] Arr.array(0, self.n) # pow_base[i] BASE^iself.pre_hash Arr.array(0, self.n 1) # pre_hash[i] hash(s[:i])self._compute_hash()def _compute_hash(self):Compute the prefix hash values and power of base values for the string.for i, b in enumerate(self.s):self.pow_base[i 1] self.pow_base[i] * self.base % self.modself.pre_hash[i 1] (self.pre_hash[i] * self.base ord(b)) % self.moddef get_sub_hash(self, l: int, r: int) - int:Get the hash value of the substring s[l:r1] return (self.pre_hash[r 1] - self.pre_hash[l] * self.pow_base[r - l 1] % self.mod self.mod) % self.moddef get_full_hash(self) - int:Get the hash value of the full stringreturn self.pre_hash[self.n]def compute_hash(self, word: str) - int:Compute the hash value of a given word using the objects base and mod.h 0for b in word:h (h * self.base ord(b)) % self.modreturn h# ————————————————————— Division line ——————————————————————class Solution:def minimumCost(self, target: str, words: List[str], costs: List[int]) - int:# Build the Trietrie Std.TrieNode()for word, cost in zip(words, costs):trie.add(word, cost)n len(target)dp Arr.array(INF, n 1)dp[0] 0# Dynamic programming to calculate the minimum costfor i in range(n):if dp[i] INF:continuefor length, cost in trie.search(target[i:]):dp[i length] min(dp[i length], dp[i] cost)return dp[n] if dp[n] ! INF else -1class Solution:def minimumCost(self, target: str, words: List[str], costs: List[int]) - int:n len(target)target_hash Std.StringHash(target)# 每个 words[i] 的哈希值 - 最小成本min_cost defaultdict(lambda: INF)for w, c in zip(words, costs):h target_hash.compute_hash(w)min_cost[h] min(min_cost[h], c)# 获取所有唯一的单词长度sorted_lens sorted(set(map(len, words)))dp Arr.array(INF, n 1)dp[0] 0for i in range(n):if dp[i] INF:continuefor sz in sorted_lens:if i sz n:break# 计算子串 target[i:isz] 的哈希值sub_hash target_hash.get_sub_hash(i, i sz - 1)dp[i sz] min(dp[i sz], dp[i] min_cost[sub_hash])return -1 if dp[n] INF else dp[n]
