题目描述

描述：给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。

如果有多个面积最大的矩形，输出任意一个均可。一个单词可以重复使用。

示例 1:

输入: ["this", "real", "hard", "trh", "hea", "iar", "sld"]
输出:
["this","real","hard"
]

示例 2:

输入: ["aa"]
输出: ["aa","aa"]

说明：

words.length <= 1000
words[i].length <= 100
数据保证单词足够随机

解题思路

思路：最直观的想法是，字典树。首先利用单词清单建立字典树，并且将单词按照长度分组，再记录一下最大单词长度方便剪枝。由于所有行等长且所有列等高，所以必定是长度相同的单词才能一起构建单词矩阵，又需要求解面积最大的单词矩阵，故优先搜索长度最长的单词分组。在搜索某一分组时，首先将该单词加入，此时可以保证按照行该单词是在字典树中的，现在只需按照列判断单词是否在字典树中，并区分是作为字典树的前缀还是作为完整的单词在字典树中，再依据此来更新最大单词矩阵面积。

//字典树类
class Trie{public://标记是否结束bool isEnd;//记录下一个节点Trie* next[26];//构造函数Trie(){isEnd=false;memset(next,0,sizeof(next));}void insert(string s){Trie* cur=this;for(int i=0;i<s.size();i++){if(!cur->next[s[i]-'a'])cur->next[s[i]-'a']=new Trie();cur=cur->next[s[i]-'a'];}cur->isEnd=true;}
};
class Solution {
public://字典树根节点Trie* root=new Trie();vector<string> res;vector<string> temp;vector<string> maxRectangle(vector<string>& words) {//单词长度 单词列表map<int,vector<string>> mp;int maxlen=0,maxarea=0,area=0;for(auto word:words){//建立字典树root->insert(word);//收集结果mp[word.size()].push_back(word);//求最大长度maxlen=max(maxlen,(int)word.size());}//反向遍历 长度从大到小for(auto it=mp.rbegin();it!=mp.rend();it++){//最长单词*宽度 不够 不用寻找if(maxlen*(it->first)<maxarea)break;temp.clear();area=0;dfs(it->second,maxarea,maxlen,area);}return res;}void dfs(vector<string>& words,int& maxarea,int& maxlen,int& area){//最大极限退出if(words[0].size()*maxlen<=maxarea)return;vector<bool> ans;//按行加入for(int i=0;i<words.size();i++){temp.push_back(words[i]);ans=isgood(temp);//可以继续往下加单词if(ans[0]){area=temp.size()*temp[0].size();//均是结束单词且较大面积if(ans[1]&&area>maxarea){maxarea=area;res=temp;}//否则继续添加单词dfs(words,maxarea,maxlen,area);}//不能else 回溯temp.pop_back();}}vector<bool> isgood(vector<string>& tp){Trie *cur;bool allend=true;int n=temp[0].size();//按列检查for(int i=0;i<n;i++){cur=root;for(int j=0;j<tp.size();j++){if(!cur->next[tp[j][i]-'a'])return {false,false};cur=cur->next[tp[j][i]-'a'];}allend&=cur->isEnd;}return {true,allend}; //可以继续插入}
};

总结：按照列判断单词是否在字典树中，此时可以返回两个参数加以区分，一个参数是是否可以继续加入单词，另一个参数是是否全部单词均已经结束。在C++中，逆序遍历map是使用mp.rbegin()和mp.rend()。