单词矩阵

该题解采用了递归和回溯的方式来尝试构造符合条件的矩形。首先通过单词初始化将所有的单词按照长度、首字母和尾字母分类存储。接着从最长的单词开始尝试作为矩形的上边，并从单词的头尾字母出发向下递归，以此构造出可能的左边、右边和下边。构建过程中采用了剪枝策略，如果当前正在构建的矩形面积已经小于已知的最大矩形面积，则停止当前分支的进一步搜索。每次成功构造出一个矩形后，检查该矩形的所有行和列是否都是有效单词，并更新最大面积和最佳矩形结果。

时间复杂度: 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