Leetcode 2977. Minimum Cost to Convert String II

• Leetcode 2977. Minimum Cost to Convert String II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2977. Minimum Cost to Convert String II

1. 解题思路

这一题思路上和前一题差不多，还是先对给定的有向图求出其中任意两点间的最短距离，然后考察字符串的变换方式。

但是，这里相较于上一题的难度在于说，这里的有向图的变换节点不再单纯是字母了，因此组合更多了。

其次的话，由于变换的节点为不定长的字符串，因此对source字符串和target字符串的变换关系可以给出不同的拆分关系，可以有不同的cost，需要对其选择最小值。

但是，即便如此，思路上来说还是很直接的，上半部分本质上和上一题一模一样，用一个Floyd算法就能直接得到。

而关于后半部分，事实上更加简单，直接使用动态规划就行。

不过，实际在处理过程中，遇到了超时的问题，因此这里做了一些剪枝的优化操作，这部分还是比较零碎的：

1. Floyd算法的算法复杂度是$O(N^3)$，因此我们需要对所有的节点进行一下去重，并且对第一层的节点提前求出了所有可能的中间节点的可能性，从而进一步进行了剪枝；
2. 对于动态规划的部分，我们引入了一个trie树，使得遍历过程可以提前终止，将整体的算法复杂度从$O(N^2)$大幅进行缩减。

但即便给出上述这些多少繁琐的剪枝操作，还是仅仅勉强通过了所有测试样例，耗时依然非常长，不知道其他大佬们是怎么处理的，看了一两个大佬们的解法，不过没有看懂就是了，唉……

2. 代码实现

给出python代码实现如下：

class Trie:def __init__(self):self.trie = {}def add_word(self, word):trie = self.triefor c in word:trie = trie.setdefault(c, {})trie["eos"] = ""class Solution:def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:n, m = len(source), len(original)costs = defaultdict(lambda: math.inf)for src, tgt, c in zip(original, changed, cost):costs[(src, tgt)] = min(c, costs[(src, tgt)])original = list(set(original))changed_set = set(changed)changed = list(changed_set)interval = [src for src in original if src in changed_set]for mid in interval:for src in original:for tgt in changed:costs[(src, tgt)] = min(costs[(src, tgt)], costs[(src, mid)] + costs[(mid, tgt)])trie = Trie()for src in original:trie.add_word(src)@lru_cache(None)def dp(idx):if idx >= n:return 0ans = math.inf_trie = trie.triesrc, tgt = "", ""for j in range(idx, n):src, tgt = src + source[j], tgt + target[j]if src == tgt:ans = min(ans, dp(j+1))elif (src, tgt) in costs:ans = min(ans, costs[(src, tgt)] + dp(j+1))if source[j] not in _trie:break_trie = _trie[source[j]]return ansans = dp(0)return ans if ans != math.inf else -1

提交代码评测得到：耗时16432ms，占用内存30.3MB。