【程序员面试金典】面试题 17.25 . 单词矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 17.25 . 单词矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

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

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

示例 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()。文章来源地址https://www.toymoban.com/news/detail-529741.html

到了这里，关于【程序员面试金典】面试题 17.25 . 单词矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！