Hello LeetCode!

难度: Hard

力扣嘉年华同样准备了纪念品展位，参观者只需要集齐 `helloleetcode` 的 `13` 张字母卡片即可获得力扣纪念章。在展位上有一些由字母卡片拼成的单词，`words[i][j]` 表示第 `i` 个单词的第 `j` 个字母。你可以从这些单词中取出一些卡片，但每次拿取卡片都需要消耗游戏代币，规则如下： - 从一个单词中取一个字母所需要的代币数量，为该字母左边和右边字母数量之积 - 可以从一个单词中多次取字母，每个字母仅可被取一次 > 例如：从 `example` 中取出字母 `a`，需要消耗代币 `2*4=8`，字母取出后单词变为 `exmple`；再从中取出字母 `m`，需要消耗代币 `2*3=6`，字母取出后单词变为 `exple`；请返回取得 `helloleetcode` 这些字母需要消耗代币的 **最少** 数量。如果无法取得，返回 `-1`。 **注意：** - 取出字母的顺序没有要求 - 取出的所有字母恰好可以拼成 `helloleetcode` **示例 1：** >输入：`words = ["hold","engineer","cost","level"]` > >输出：`5` > >解释：最优方法为： >从 `hold` 依次取出 `h`、`o`、`l`、`d`，代价均为 `0` >从 `engineer` 依次取出第 `1` 个 `e` 与最后一个 `e`，代价为 `0` 和 `5*1=5` >从 `cost` 取出 `c`、`o`、`t`，代价均为 `0` >从 `level` 依次取出 `l`、`l`、`e`、`e`，代价均为 `0` >所有字母恰好可以拼成 `helloleetcode`，因此最小的代价为 `5` **示例 2：** >输入：`words = ["hello","leetcode"]` > >输出：`0` **提示：** + `n == words.length` + `m == words[i].length` + `1 <= n <= 24` + `1 <= m <= 8` + `words[i][j]` 仅为小写字母

Submission

运行时间: 1128 ms

内存: 22.0 MB

value = [[32] * (1 << ln) for ln in range(9)]
for ln in range(9):
    value[ln][0] = 0
    for mask in range(1, 1 << ln):
        left, right, bm = ln - 1, 0, 1
        while bm <= mask:
            if mask & bm:
                pm = ((mask & ~(bm * 2 - 1)) >> 1) | mask & (bm - 1)
                value[ln][mask] = min(value[ln][mask], value[ln - 1][pm] + left * right)
            left -= 1; right += 1; bm <<= 1

key = "helloleetcode"
chset, kln = set(key), len(key)
next_st = [defaultdict(int) for _ in range(1 << kln)]
for mask in range(1 << kln):
    for j, c in enumerate(key):
        if mask & (1 << j) == 0:
            next_st[mask][c] = mask | (1 << j)

M, INF = 1 << kln, 123456789

class Solution:
    def Leetcode(self, words: List[str]) -> int:
        dp = defaultdict(lambda: INF)
        dp[0] = 0
        for s in words:
            ln = len(s)
            for mask, cost in list(dp.items()):
                def dfs(at, choice, cur):
                    if at >= ln:
                        if dp[cur] > (tr := cost + value[ln][choice]): dp[cur] = tr
                        return
                    dfs(at + 1, choice, cur)
                    nxt = next_st[cur][s[at]]
                    if nxt > 0:
                        dfs(at + 1, choice | (1 << at), nxt)
                dfs(0, 0, mask)
        return dp[M - 1] if (M - 1 in dp) else -1

Explain

此题解采用了动态规划和状态压缩的策略。首先，创建一个数组 'value' 来存储从给定单词中取出特定字母序列的最小代价。该数组通过动态规划更新，考虑所有可能的字母组合和相应的消耗。对于每个单词，'value' 数组考虑所有子序列（使用位掩码表示）并计算从这些子序列中获取特定字母的代价。接着，对于目标字符串 'helloleetcode'，构造一个转移矩阵 'next_st'，该矩阵记录了在当前状态下添加一个新字符后可能达到的新状态。在主函数 'Leetcode' 中，使用一个字典 'dp' 来动态记录从每个单词中取出特定字母序列以拼成目标字符串的最小总代价。遍历每个单词，并递归地考虑取或不取当前字符的情况，通过比较不同选择的代价来更新 'dp'。最终，'dp' 中的最小值就是答案。

时间复杂度: O((m * 2^m) + (k * 2^k) + (n * m^2 * 2^k))

空间复杂度: O(m * 2^m + k * 2^k + 2^k)

value = [[32] * (1 << ln) for ln in range(9)]  # 初始化动态规划数组，用于计算从单词中取出字母的最小代价
for ln in range(9):  # 遍历每种可能的单词长度
    value[ln][0] = 0  # 空选择的代价为0
    for mask in range(1, 1 << ln):  # 遍历所有可能的字母组合
        left, right, bm = ln - 1, 0, 1  # 初始化左右指针和位掩码
        while bm <= mask:  # 遍历所有位
            if mask & bm:  # 如果当前位在掩码中
                pm = ((mask & ~(bm * 2 - 1)) >> 1) | mask & (bm - 1)  # 计算取出当前字母后的新掩码
                value[ln][mask] = min(value[ln][mask], value[ln - 1][pm] + left * right)  # 更新代价
            left -= 1; right += 1; bm <<= 1  # 更新左右指针和位掩码

key = 'helloleetcode'  # 目标字母序列
chset, kln = set(key), len(key)  # 构造目标字母集合和长度
next_st = [defaultdict(int) for _ in range(1 << kln)]  # 初始化状态转移数组
for mask in range(1 << kln):  # 遍历所有状态
    for j, c in enumerate(key):  # 遍历目标字母序列
        if mask & (1 << j) == 0:  # 如果当前字母未被选择
            next_st[mask][c] = mask | (1 << j)  # 更新状态

M, INF = 1 << kln, 123456789  # 定义最终状态掩码和无穷大值

class Solution:
    def Leetcode(self, words: List[str]) -> int:
        dp = defaultdict(lambda: INF)  # 初始化动态规划字典
        dp[0] = 0  # 初始状态代价为0
        for s in words:  # 遍历所有单词
            ln = len(s)  # 获取单词长度
            for mask, cost in list(dp.items()):  # 遍历当前所有状态和代价
                def dfs(at, choice, cur):  # 定义深度优先搜索函数
                    if at >= ln:  # 如果遍历完单词
                        if dp[cur] > (tr := cost + value[ln][choice]): dp[cur] = tr  # 更新状态代价
                        return
                    dfs(at + 1, choice, cur)  # 不选择当前字母
                    nxt = next_st[cur][s[at]]  # 获取添加当前字母后的新状态
                    if nxt > 0:
                        dfs(at + 1, choice | (1 << at), nxt)  # 选择当前字母
                dfs(0, 0, mask)  # 从单词首字母开始搜索
        return dp[M - 1] if (M - 1 in dp) else -1  # 返回最终状态的最小代价，如果不可能则返回-1

Explore

在动态规划中使用位掩码来表示字母的选择，主要是因为位掩码允许我们以非常紧凑和高效的方式来表示和操作字母组合的状态。每个位（bit）可以代表一个字母是否被选择（1表示选中，0表示未选中），这样就可以使用整数的位运算（如位与、位或和位非）来快速处理状态的转移。这种方法的优势在于：1) 存储效率高，一个整数可以表示多个字母的选择状态；2) 计算效率高，位运算通常比其他类型的数据操作更快；3) 易于实现状态转移，可以直接通过位操作实现状态的添加和检查。

在计算`value[ln][mask]`时，每个位掩码`mask`代表了从单词中选择字母的不同组合，而`left * right`代表的是选择当前字母的代价。这里，`left`和`right`分别表示当前字母左侧和右侧未被选择的字母数量。当选择一个字母时，左侧未选择的字母数量和右侧未选择的字母数量的乘积可以被视作这次选择的'代价'，因为它反映了这个字母在单词中的'位置重要性'。具体来说，如果一个字母被选择，那么它左侧和右侧的未选择字母越多，意味着它在原单词中的位置越靠中间，其选择可能导致的组合变化和影响更大，因此代价也就更高。

在`next_st`数组的计算中，每个状态代表了目标字符串`helloleetcode`中已经被选择的字母集合。数组的索引使用位掩码表示，每个位对应目标字符串中的一个字符，如果该位为1，则表示相应位置的字符已被选择。转移逻辑是：对于每个当前状态（位掩码），遍历目标字符串中的每个字符。如果当前字符在状态中未被选择（对应位为0），则通过位或运算将该字符的位设为1，从而生成一个新状态。这个新状态表示在当前选择的基础上，又选择了一个新的字符。这样，`next_st`数组通过记录每个状态可以转移到的所有可能的新状态，使得我们可以在动态规划中，根据当前已选择的字符集合，直接查找到添加任一新字符后的新状态。