题目难度: 困难
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。
如果有多个面积最大的矩形，输出任意一个均可。一个单词可以重复使用。
示例 1:
- 输入: ["this", "real", "hard", "trh", "hea", "iar", "sld"]
- 输出:
[
"this",
"real",
"hard"
]
示例 2:
- 输入: ["aa"]
- 输出: ["aa","aa"]
说明：
- words.length <= 1000
- words[i].length <= 100
- 数据保证单词足够随机
题目思考
- 需要使用哪些数据结构?
- 如何优化时间复杂度?
解决方案
思路
- 这道题很有难度, 因为有很多限定条件, 且数据规模不小, 再加上单词还可以重复使用
- 所以直接暴力回溯的话, 会有茫茫多种可能性, 时间复杂度过高, 那如何进行优化呢?
- 对于字符串类的问题, 很多情况下我们都可以尝试使用字典树(trie)来进行优化, 这道题也同样适用
- 首先我们将所有单词加入字典树中, 并额外维护一个单词宽度到对应单词列表的映射字典
- 接下来我们遍历每个单词宽度, 初始传入单词宽度数目个根节点, 以及空的矩阵
- 然后开始回溯, 遍历当前宽度对应的所有单词, 判断该单词是否可以作为新的一行添加到矩阵中 (利用 trie 节点来判断), 是的话就可以继续递归调用了
- 同时如果新增该单词后, 所有列都形成了完整单词, 那么意味着可以形成有效矩阵了, 若其面积更大, 则更新最终结果即可
- 另外还有个优化, 我们可以从大到小开始遍历单词宽度, 这样如果当前宽度对应的最大面积不超过之前已经得到的最大面积时, 就无需继续遍历了
- 下面代码有非常详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(M^W): 假设单词的平均宽度为 W, 每个宽度对应的单词平均个数为 M, 由于每次回溯最多需要尝试 M 种可能性, 然后最多要回溯 W 次, 所以是O(M^W), 由于题目保证单词足够随机, 所以基数 M 的值不会很大 - 空间复杂度
O(NW): 假设单词数目为 N, 单词的平均宽度为 W, 由于字典树和宽度映射字典都需要存储所有字符, 所以是O(NW)
代码
# 字典树+width2words字典+dfs固定宽度节点列表
class Node:
def __init__(self, c=None):
self.c = c
self.children = {}
self.isWord = False
class Trie:
def __init__(self):
self.root = Node()
def addWord(self, w):
cur = self.root
for c in w:
if c not in cur.children:
cur.children[c] = Node(c)
cur = cur.children[c]
cur.isWord = True
class Solution:
def maxRectangle(self, words: List[str]) -> List[str]:
trie = Trie()
width2words = collections.defaultdict(list)
for w in words:
# 记录单词宽度到单词本身的映射关系
width2words[len(w)].append(w)
# 加入字典树中
trie.addWord(w)
maxArea = 0
res = []
def dfs(nodes, board):
nonlocal maxArea, res
width = len(nodes)
for w in width2words[width]:
# 遍历所有宽度为width的单词
for i, c in enumerate(w):
if c not in nodes[i].children:
# 如果当前字符无法作为当前节点的子节点, 则说明w不能追加作为新的一行, 跳出循环
break
else:
# 此时说明w可以追加作为新的一行
newNodes = []
newBoard = board + [w]
# 接下来检查追加完w后, 是否能组成一个有效的矩阵 (即每一列都是完整单词)
canFormMatrix = True
for i, c in enumerate(w):
child = nodes[i].children[c]
newNodes.append(child)
if not child.isWord:
# 当前列还不是完整单词, 不能形成矩阵
canFormMatrix = False
if canFormMatrix and width * len(newBoard) > maxArea:
# 可以形成新的矩阵, 且面积更大 => 更新最终结果
maxArea = width * len(newBoard)
res = newBoard
dfs(newNodes, newBoard)
# 从大到小遍历宽度, 用于剪枝
for width in sorted(width2words)[::-1]:
if width * width <= maxArea:
# 剪枝, 若高度大于当前宽度, 则一定会在之前的遍历中被计算
# 所以当前宽度对应的最大面积就是width*width, 如果已经得到的最大面积大于该值, 则无需继续计算了
break
# 初始化长度为width的根节点列表, 代表宽度为width的单词的每个字符在当前行对应的字典树节点
dfs([trie.root] * width, [])
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号