0411：最短独占单词缩写（★★★）

2016-02-15 约 973 字预计阅读 2 分钟次阅读

力扣第 411 题

题目

通过将任意数量的 不相邻 子字符串替换为它们的长度，可以完成对字符串的缩写。例如，像 "substitution" 这样的字符串可以缩写为（但不限于）：

"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (不替换子字符串)

注意："s55n" ("s ubsti tutio n") 不是 "substitution" 的有效缩写形式，因为它试图替换两个相邻的子字符串。

缩写的长度是未被替换的字母数加上被替换的字符串数。例如，缩写 "s10n" 的长度为 3（2 个字母 + 1 个子字符串），而 "su3i1u2on" 的长度为 9（6 个字母 + 3 子字符串）。

给你一个目标字符串 target 和一个字符串数组 dictionary 作为字典，为 target 找出并返回一个最短长度的缩写字符串，同时这个缩写字符串不是字典 dictionary 中其他字符串的缩写形式。如果有多个有效答案，可以返回其中任意一个。

示例 1：

输入：target = "apple", dictionary = ["blade"]
输出："a4"
解释："apple" 的最短缩写形式为 "5" ，但这也是 "blade" 的缩写形式之一。
下一组最短缩写是 "a4" 和 "4e" ，其中 "4e" 也是 "blade" 的缩写形式之一，而 "a4" 不是。
因此，返回 "a4" 。

示例 2：

输入：target = "apple", dictionary = ["blade","plain","amber"]
输出："1p3"
解释："5" 同时是 "apple" 和字典中所有单词的缩写形式。
"a4" 同时是 "apple" 和 "amber" 的缩写形式。
"4e" 同时是 "apple" 和 "blade" 的缩写形式。
"1p3"、"2p2" 和 "3l1" 是 "apple" 的下一组最短缩写形式。
因为它们不是字典中其他单词的缩写形式，返回其中任意一个都是正确的。

提示：

target.length == m
dictionary.length == n
1 <= m <= 21
0 <= n <= 1000
1 <= dictionary[i].length <= 100
如果 n > 0 ，那么 log₂(n) + m <= 21
target 和 dictionary[i] 仅包含小写字符

分析

#1 状压

0408 进阶版。

每一种缩写状态都可以压缩为一个数 st，二进制的 1/0 代表该位置是否保留
遍历缩写状态 st，判断该状态是否有效（字典单词都和 target 的缩写不同）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
        def gen(w,st):
            res, cnt = '', 0
            for i in range(m):
                if st&(1<<i):
                    res += str(cnt or '')+w[i]
                    cnt = 0
                else:
                    cnt += 1
            return res+str(cnt or '')

        m = len(target)
        A = [w for w in dictionary if len(w)==m]
        if not A:
            return str(m)
        res = target
        for st in range(1<<m):
            x = gen(target,st)
            if len(x)<len(res) and all(gen(w,st)!=x for w in A):
                res = x
        return res

520 ms

#2 状压+预处理

还有种巧妙的方法判断某种缩写状态 st 是否有效：

想想两个单词什么情况下的缩写形式会相同，保留的位置上的字符都相同
那么提前计算单词和 target 相同位置的状态表示 st2，如果 st 不是 st2 的子集，即代表缩写形式不同

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
        def gen(st):
            res, cnt = '', 0
            for i in range(m):
                if st&(1<<i):
                    res += str(cnt or '')+target[i]
                    cnt = 0
                else:
                    cnt += 1
            return res+str(cnt or '')

        m = len(target)
        same = lambda w1,w2: sum(1<<i for i,(a,b) in enumerate(zip(w1,w2)) if a==b)
        A = {same(target,w) for w in dictionary if len(w)==m}
        if not A:
            return str(m)
        return min([gen(st) for st in range(1<<m) if all(st|st2!=st2 for st2 in A)],key=len)

$O((N+M)*2^M)$，72 ms

目录

0411：最短独占单词缩写（★★★）

题目

分析

#1 状压

#2 状压+预处理

解答