这里是题目描述：17.25.单词矩阵
本题在LeetCode官网上的难度等级为hard。
首先将words中的单词按长度来整理；
然后使用基于 回溯 的解法，按单词长度来穷举可能的单词矩阵，判断并更新最大面积矩阵，在穷举的过程中注意“剪枝”（具体剪枝策略详见代码）；
此外，把words中的所有单词存入 字典树 当中，用于检查每个可能的矩阵是合法，即矩阵的纵列是否也是word中的单词，如果矩阵某个纵列中出现了不是words中单词的字母序列提前剪枝，如果矩阵所有纵列中的单词序列都是word中的字母序列，判断是否所有纵列都形成了单词，如果都形成了单词，计算当前矩阵大小，并更新面积最大单词矩阵
题解代码：
class Solution { class TrieNode //字典树节点 { int val; boolean leaf; TrieNode[] children; public TrieNode(int val) { this.val = val; this.leaf = false; this.children = new TrieNode[26]; } } TrieNode root; //字典树根节点 int maxLen; //记录最长单词的长度 int maxArea; //记录找到的最大面积 HashMap<Integer,Set<String>> map; //按单词长度整理word中的单词 ArrayList<String> ans; public String[] maxRectangle(String[] words) { if(words.length==0) { return new String[0]; } root=constructTrie(words); maxLen=0; map=new HashMap<>(); ans=new ArrayList<>(); for(String w:words) { maxLen=Math.max(maxLen,w.length()); Set<String> set=map.getOrDefault(w.length(),new HashSet<>()); set.add(w); map.put(w.length(),set); } for(int key:map.keySet()) //尝试每个长度作为矩阵横行的长度 { dfs(map.get(key),key,new ArrayList<>()); } return ans.toArray(new String[ans.size()]); //转化成数组 } void dfs(Set<String> set,int key,ArrayList<String> path) //深度优先搜索回溯，在矩阵横行长度为key时寻找可能的面积最大的矩形 { if(key*maxLen<maxArea) //剪枝，当前的长度key不可能获得最大面积矩阵 { return; } if(path.size()>maxLen) //不可能在矩阵纵列上长度大于maxArea的单词，退出 { return; } //开始尝试每个单词 for(String w:set) { path.add(w); boolean[] valid=isValid(path); if(valid[0]) { if(valid[1] && maxArea<path.size()*key) //更新最大面积矩阵 { maxArea=path.size()*key; ans=new ArrayList<>(path); } dfs(set,key,path); //继续进行下一层（矩阵中下一横行）的尝试 } path.remove(path.size()-1); //移除当前path尾部 } } /** 判断一个矩阵是否每一列形成的单词都在清单里 * 存在两种情况：1.有的列中的字母不在字典树中，即这一列不可能构成单词，整个矩阵不合要求 * 2.每列的所有字母都在字典树中但有的结尾不是leaf，也就是有的列目前还不是个单词 * 所以需要一个boolean数组res[]来存放结果： * res[0]表示是否有字母不在字典树中，true:都在，false:有不在的 * res[1]表示是否所有的列都构成了清单里的单词 */ boolean[] isValid(ArrayList<String> path) { int m=path.size(); int n=path.get(0).length(); boolean[] res={true,true}; //检查path中的每个纵列 for(int j=0;j<n;j++) { TrieNode node=root; for(int i=0;i<m;i++) { int num=path.get(i).charAt(j)-'a'; if(node.children[num]==null) //出现了字典树中没有的单词 { return new boolean[] {false,false}; } node=node.children[num]; } if(!node.leaf) //这个纵列的所有字母都在字典树中，但是没有形成一个单词 { res[1]=false; } } return res; } TrieNode constructTrie(String[] word) //构建字典树 { TrieNode root=new TrieNode(-1); for(String w:word) { TrieNode node=root; for(int i=0;i<w.length();i++) { char ch=w.charAt(i); int num=ch-'a'; if(node.children[num]==null) { node.children[num]=new TrieNode(num); } node=node.children[num]; } node.leaf=true; } return root; } }