golang 解法, 执行用时: 148 ms, 内存消耗: 45.5 MB, 提交时间: 2023-04-22 12:49:43

// 前缀树
type TrieNode struct {
	IsLeaf   bool
	Children [26]*TrieNode
}

// 插入一个单词
func (t *TrieNode) Insert(s string) {
	cur := t
	for _, r := range s {
		i := r - 'a'
		if cur.Children[i] == nil {
			cur.Children[i] = &TrieNode{}
		}
		cur = cur.Children[i]
	}
	cur.IsLeaf = true
}

func maxRectangle(words []string) []string {
	trie := &TrieNode{}
	wordsByLength := make(map[int][]string)
	maxLen := 0
	for _, word := range words {
		trie.Insert(word)
		l := len(word)
		wordsByLength[l] = append(wordsByLength[len(word)], word)
		if l > maxLen {
			maxLen = l
		}
	}


	tries := make([]*TrieNode, maxLen)
	for i := 0; i < len(tries); i++ {
		tries[i] = trie
	}
	var ans []string
	// 我们的迭代策略是，从大到小迭代每个长度l，每次仅考虑  lx1 lx2 ... lx(l-1) lxl 的情况，
    // 那么是否会漏掉 lx(l+n)的情况呢？并不会。如果l是最大长度，那么这种情况一定不满足条件，
    // 因为纵列的长度已经超过了最大单词长度。如果l不是最大长度，当l+n大于最大单词长度，
    // 不满足要求，当l+n不大于最大单词长度，那么在 l+n那一轮循环中，已经考虑过 lx(l+n)这个情况了
	// 为什么不从小到大迭代呢？因为较长的单词构成较大的矩形的几率比较高，利于后面剪枝。
	for l := maxLen; l > 0; l-- {
		if l*l <= area(ans) {
			break
		}
		if _, ok := wordsByLength[l]; !ok {
			continue
		}
		getRectangles(wordsByLength[l], 0, []string{}, tries, &ans)
	}
	return ans
}

func getRectangles(words []string, i int, rectangle []string, tries []*TrieNode, ans *[]string) {
	length := len(words[0])
	for _, word := range words {

		// 这里也有一个很大的优化点。如果直接初始化一个长度为len(tries)的数组出来，耗时会翻倍
        // 应该是因为我们的大量尝试中，满足条件的其实并不多，大部分尝试都会失败，所以这里没有必要直接初始化一个数组出来
		var nextTries []*TrieNode
		valid, allLeaf := true, true
		for i := 0; i < length; i++ {
			nextTrie := tries[i].Children[word[i]-'a']
			if nextTrie == nil {
				valid = false
				break
			}
			nextTries = append(nextTries, nextTrie)
			if !nextTrie.IsLeaf {
				allLeaf = false
			}
		}
		if valid {
			rectangle = append(rectangle, word)
			if allLeaf && area(rectangle) > area(*ans) {
				*ans = make([]string, len(rectangle))
				copy(*ans, rectangle)
			}
			if i+1 < length {
				getRectangles(words, i+1, rectangle, nextTries, ans)
			}
			rectangle = rectangle[:len(rectangle)-1]
		}
	}
}

// 计算矩形面积
func area(rectangle []string) int {
	if rectangle == nil {
		return 0
	}
	return len(rectangle) * len(rectangle[0])
}

python3 解法, 执行用时: 2256 ms, 内存消耗: 30 MB, 提交时间: 2023-04-22 12:49:05

class Trie:
    def __init__(self):
        self.root = [{}, False]
    
    def addWord(self, word):
        cur = self.root
        for c in word:
            if c not in cur[0]:
                cur[0][c] = [{}, False]
            cur = cur[0][c]
        cur[1] = True

class Solution:
    def maxRectangle(self, words: List[str]) -> List[str]:
        area = 0
        res = []
        trie = Trie()
        for word in words:
            trie.addWord(word)

        def dfs(arr, li):
            for word in words:
                if len(word) != len(arr):   continue
                for i, c in enumerate(word):
                    if c not in arr[i][0]: break
                else:
                    temp = arr[:]
                    flag = True
                    for i, c in enumerate(word):
                        temp[i] = temp[i][0][c]
                        flag &= temp[i][1]
                    li.append(word)
                    if flag:
                        h, w = len(li), len(word)
                        nonlocal area, res
                        if h * w > area:
                            area = h * w
                            res = li[:]
                    dfs(temp, li)
                    li.pop()

        ll = sorted(set(len(word) for word in words), reverse = True)
        for l in ll:
            if l * ll[0] < area:   break
            dfs([trie.root] * l, [])
        return res

python3 解法, 执行用时: 732 ms, 内存消耗: 26.7 MB, 提交时间: 2023-04-22 12:48:49

class Solution:
    def maxRectangle(self, words: List[str]) -> List[str]:
        words = set(words)
        d = {}
        tree = {}#字典树
        m = 0#最大单词长度
        for word in words:
            l = len(word)
            if l not in d:#将单词按照长度分组
                d[l] = set()
            d[l].add(word)
            m = max(m, l)#更新最大单词长度
            tmp = tree
            for n in word:
                if n not in tmp:
                    tmp[n] = {}
                tmp = tmp[n]
            tmp["label"] = 0
        def dfs(trees):#参数为字典树列表
            t = True #是否组成单词并结束
            ans = []
            m = -1#组成的最大矩形面积
            for i in trees:
                if "label" not in i:#如果不能组成单词
                    t = False #无法结束
            for word in words:#遍历指定长度单词列表
                x = []
                lb = True#单词是否可以铺满一层
                for i, n in enumerate(word):
                    if n not in trees[i]:
                        lb = False
                        break
                    x.append(trees[i][n])
                if lb:#如果可以铺满一层，继续向下深搜
                    res = dfs(x)
                    s = 0 if not res[0] else len(res[0]) * len(res[0][0])
                    if res[1] and m < s:
                        ans = [word] + res[0]
                        t = True
                        m = s
            return ans, t
        n = 0
        res = []
        for i in sorted(d.keys(), reverse = True):#对单词长度降序遍历
            if i * m <= n:#剪枝，当前长度和最大单词长度最成的矩形面积更小时跳出
                return res
            words = d[i]#指定长度的单词列表
            f = dfs([tree for p in range(i)])
            if f[1] and len(f[0]) * len(f[0][0]) > n:
                res = f[0]
                n = len(f[0]) * len(f[0][0])
        return res

java 解法, 执行用时: 55 ms, 内存消耗: 52.1 MB, 提交时间: 2023-04-22 12:48:23

class Solution {
    class Trie{
        boolean isEnd = false;
        Trie[] child = new Trie[26];
    }
    void add(String s){
        Trie cur = root;
        for(char c : s.toCharArray()){
            int n = c - 'a';
            if(cur.child[n] == null) cur.child[n] = new Trie();
            cur = cur.child[n];
        }
        cur.isEnd = true;
    }
    Trie root;
    //用max保存当前最大矩形面积
    int max = -1;
    //用哈希表保存各个长度字符串的集合
    Map<Integer, List<String>> map = new HashMap<>();
    List<String> ans = new ArrayList<>();
    public String[] maxRectangle(String[] words) {
        this.root = new Trie();
        int n = words.length;
        for(String w : words){
            add(w);
            map.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
        }
        //按照字符串长度从大到小排序
        Arrays.sort(words, (a, b) -> b.length() - a.length());
        for(int i = 0; i < n; i++){
            Trie cur = root;
            String w = words[i];
            //用curList保存矩形的每个字符串
            List<String> curList = new ArrayList<>();
            curList.add(w);
            //用list保存当前可能形成矩形的字符串在字典树中的当前结点
            List<Trie> list = new ArrayList<>();
            int len = w.length();
            //如果当前长度的积不大于最大矩形面积，则退出
            //因为从最大到最小排序，其中4 * 3的字符串矩阵和3 * 4的矩阵是相同的，可以进行去重
            if(len * len <= max) break;
            //check检测是否能组成矩形，flag检测是否可能组成更大的矩形
            boolean check = true, flag = true;
            for(int j = 0; j < len; j++){
                int c = w.charAt(j) - 'a';
                if(cur.child[c] != null){
                    //判断当前字符串是否所有结点都为叶结点，即能组成字符串
                    if(!cur.child[c].isEnd) check = false;
                    list.add(cur.child[c]);
                }else{
                    //如果字符串没有对应子结点，则无法组成矩形
                    check = false;
                    flag = false;
                    break;
                }
            }
            //如果当前字符串可以组成矩形，则进入dfs
            if(flag){
                dfs(1, len, curList, list);
            }
            //如果当前字符串所有结点都可以为叶结点，则判断当前矩形是否最大
            if(check && max == -1){
                max = len;
                ans = curList;
            }
        }
        int size = ans.size();
        String[] strs = new String[size];
        for(int i = 0; i < size; i++) strs[i] = ans.get(i);
        // System.out.println(max);
        return strs;
    }
    void dfs(int cur, int len, List<String> curList, List<Trie> list){
        if(cur == len){
            return;
        }
        //各种结点判断同上
        for(String w : map.get(len)){
            boolean check = true, flag = true;
            //其中next保存下一个可能形成矩形的字典树结点集合
            List<Trie> next = new ArrayList<>();
            //nextList保存下一个可能形成矩形的字符串集合
            List<String> nextList = new ArrayList<>();
            for(int i = 0; i < len; i++){
                int c = w.charAt(i) - 'a';
                Trie ct = list.get(i);
                if(ct.child[c] != null){
                    if(!ct.child[c].isEnd) check = false;
                    next.add(ct.child[c]);
                }else{
                    check = false;
                    flag = false;
                    break;
                }
            }
            if(flag){
                // System.out.println(w);
                nextList.addAll(curList);
                nextList.add(w);
                dfs(cur + 1, len, nextList, next);
            }
            if(check && len * (cur + 1) > max){
                max = len * (cur + 1);
                ans = nextList;
            }
        }
    }
}