该题解采用了递归和回溯的方式来尝试构造符合条件的矩形。首先通过单词初始化将所有的单词按照长度、首字母和尾字母分类存储。接着从最长的单词开始尝试作为矩形的上边,并从单词的头尾字母出发向下递归,以此构造出可能的左边、右边和下边。构建过程中采用了剪枝策略,如果当前正在构建的矩形面积已经小于已知的最大矩形面积,则停止当前分支的进一步搜索。每次成功构造出一个矩形后,检查该矩形的所有行和列是否都是有效单词,并更新最大面积和最佳矩形结果。
时间复杂度: O(n^L)(理论最坏情况)
空间复杂度: O(n)
# Definition of Solution class which handles the rectangle creation problem
class Solution:
def __init__(self):
self.words = []
self.word_map = dict() # Stores words grouped by length, start and end character
self.word_all = dict() # Dictionary to check the existence of a vertical word directly
self.word_len_max = 2 # Tracks the maximum length of words encountered
self.ans_rect = None # Stores the largest found rectangle
self.ans_area = 0 # Tracks the area of the largest found rectangle
def maxRectangle(self, words: [str]) -> [str]:
self.words = words
self.add_word_to_map() # Organize words in maps
self.check_up_edge() # Begin attempting to form rectangles from potential top edges
return self.ans_rect
def add_word_to_map(self):
# Initialize word mappings
for word_pos, word in enumerate(self.words):
word_length = len(self.words[word_pos])
word_head = self.words[word_pos][:1] # First character of word
word_end = self.words[word_pos][-1:] # Last character of word
if word_length not in self.word_map.keys():
self.word_map[word_length] = dict()
if word_head not in self.word_map[word_length].keys():
self.word_map[word_length][word_head] = dict()
if word_end not in self.word_map[word_length][word_head].keys():
self.word_map[word_length][word_head][word_end] = []
self.word_map[word_length][word_head][word_end].append(word_pos)
self.word_all[word] = word_pos
if word_length > self.word_len_max:
self.word_len_max = word_length
def check_up_edge(self):
# Begin with potential top edges of the largest size and work downwards
for up_edge_len in range(self.word_len_max, 1, -1):
if up_edge_len * self.word_len_max <= self.ans_area:
break
if up_edge_len in self.word_map:
for up_edge_head in self.word_map[up_edge_len]:
for up_edge_end in self.word_map[up_edge_len][up_edge_head]:
for up_edge_word_pos in self.word_map[up_edge_len][up_edge_head][up_edge_end]:
self.check_left_edge(self.words[up_edge_word_pos]) # Attempt to form a left edge
def check_left_edge(self, up_edge_word):
# For each potential top edge, try to form a valid left edge
for left_edge_len in range(self.word_len_max, 1, -1):
if len(up_edge_word) * left_edge_len <= self.ans_area:
break
if left_edge_len in self.word_map:
left_edge_head = up_edge_word[:1] # The first character must match the first of the top edge
if left_edge_head in self.word_map[left_edge_len]:
for left_edge_end in self.word_map[left_edge_len][left_edge_head]:
for left_edge_word_pos in self.word_map[left_edge_len][left_edge_head][left_edge_end]:
self.check_right_edge(up_edge_word, self.words[left_edge_word_pos]) # Check if a valid right edge can be formed
def check_right_edge(self, up_edge_word, left_edge_word):
# Matching a right edge with the same length as the left and starting with the last character of the top edge
right_edge_len = len(left_edge_word)
right_edge_head = up_edge_word[-1:]
if right_edge_head in self.word_map[right_edge_len]:
for right_edge_end in self.word_map[right_edge_len][right_edge_head]:
for right_edge_word_pos in self.word_map[right_edge_len][right_edge_head][right_edge_end]:
self.check_down_edge(up_edge_word, left_edge_word, self.words[right_edge_word_pos]) # Finally, attempt to find a valid bottom edge
def check_down_edge(self, up_edge_word, left_edge_word, right_edge_word):
# Match the bottom edge starting with the last character of the left edge and ending with the last of the right
down_edge_len = len(up_edge_word)
down_edge_head = left_edge_word[-1:]
down_edge_end = right_edge_word[-1:]
if down_edge_head in self.word_map[down_edge_len]:
if down_edge_end in self.word_map[down_edge_len][down_edge_head]:
for down_edge_word_pos in self.word_map[down_edge_len][down_edge_head][down_edge_end]:
self.check_frame(up_edge_word, left_edge_word, right_edge_word, self.words[down_edge_word_pos]) # Assess if the completed frame can form a valid rectangle
def check_frame(self, up_edge_word, left_edge_word, right_edge_word, down_edge_word):
# Fast initial check if the rectangle holds potential before verifying each possible configuration
demo_box = self.quick_check(up_edge_word, left_edge_word, right_edge_word, down_edge_word)
if not demo_box:
return
check_ans = self.full_check(demo_box) # Detailed verification of each configuration to finalize the best rectangle
if check_ans:
self.ans_rect = check_ans
self.ans_area = len(check_ans) * len(check_ans[0])
def quick_check(self, up_edge_word, left_edge_word, right_edge_word, down_edge_word):
# Preliminary check for column validity before finalizing the row configurations
for col in range(1, len(up_edge_word) - 1):
if not self.find_str_by(len(left_edge_word), up_edge_word[col:col + 1], down_edge_word[col:col + 1]):
return None
demo_box = [[up_edge_word]]
for row in range(1, len(left_edge_word) - 1):
find_res = self.find_str_by(len(up_edge_word), left_edge_word[row:row + 1], right_edge_word[row:row + 1])
if not find_res:
return None
else:
demo_box.append(find_res)
demo_box.append([down_edge_word])
return demo_box
def find_str_by(self, str_len, str_head, str_end):
# Retrieve a list of words based on specific length and start/end character
if str_len in self.word_map:
if str_head in self.word_map[str_len]:
if str_end in self.word_map[str_len][str_head]:
return list(map(lambda x: self.words[x], self.word_map[str_len][str_head][str_end]))
return None
def full_check(self, demo_box, line=0):
# Recursive verification of every possible row configuration to finalize the rectangle
if line >= len(demo_box):
word_box = list(map(lambda x: x[0], demo_box))
if self.box_check(word_box):
return word_box
else:
return None
for str_canbe in demo_box[line]:
box_copy = copy.deepcopy(demo_box)
box_copy[line] = [str_canbe]
check_res = self.full_check(box_copy, line + 1)
if check_res:
return check_res
return None
def box_check(self, word_box):
# Final check for vertical word validity in the formed rectangle
for col in range(1, len(word_box[0]) - 2):
check_word = ""
for row in range(0, len(word_box)):
check_word += word_box[row][col]
if check_word not in self.word_all:
return False
return True