CC

自然万物都趋向从有序变得无序

0%

leetcode-面试题 17.25 单词矩阵(字典树+dfs)

发表于 更新于 分类于 Valine：

面试题 17.25. 单词矩阵 - 力扣（LeetCode） (leetcode-cn.com)

题意

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

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

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

思路

首先，很直观的思路是枚举单词矩阵的每一行的单词，判断判断单词句子每一行单词长度是否相同，判断每一列是否是一个单词，如果条件都满足，则找出满足条件的面积最大的矩阵。

于是就有了以下思路：对于所有单词按长度分组，每次枚举同一的单词，这样可以保证每一行的单词都相同。之后使用dfs枚举每一行的单词，并且判断每次组成的单词矩阵的每一列是否是一个单词，如果都是则更新答案。

优化：

  • 每次的单词矩阵的每一列必须保证是某个单词或者某个单词的一个前缀，才能继续枚举，此过程可以使用字典树

  • 当矩阵高度大于等于单词最大长度时则不再枚举

  • 当前矩阵的宽度乘以最大单词长度小于当前最大单词矩阵面积则不再枚举，即就算可以组成单词矩阵也不会比之前最大的单词矩阵面积大

  • 按长度从大到小枚举单词

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//
// Created by cb on 2021/12/28.
//

#include "string"
#include "vector"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "unordered_map"
#include "map"
#include "unordered_set"

using namespace std;

class TrieNode {
public:
    TrieNode *next[26];
    bool isWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) next[i] = nullptr;
        isWord = false;
    }

//    ~TrieNode() {
//        for (int i = 0; i < 26; i++) delete next[i];
//    }
};

class Trie {
public:
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }

//    ~Trie() {
//        delete root;
//    }

    void insert(string word) {
        TrieNode *cur = root;
        for (auto &x: word) {
            if (cur->next[x - 'a'] == nullptr)
                cur->next[x - 'a'] = new TrieNode();
            cur = cur->next[x - 'a'];
        }
        cur->isWord = true;
    }
};


class Solution {
public:
    vector<string> ans, finalAns;
    int maxlen;
    int maxarea;
    map<int, unordered_set<string>, greater<>> len2string;
    Trie p;
    vector<string> maxRectangle(vector<string> &words) {
        maxlen = 0;
        maxarea = 0;
        for (auto &x: words) {
            p.insert(x);
            len2string[int(x.size())].insert(x);
            maxlen = max(maxlen, int(x.size()));
        }
        for (auto &x: len2string) {
            ans.clear();
            dfs(x.first);
        }
        return finalAns;
    }

    vector<bool> check(int m) {
        int n = ans.size();
        bool flag = true;
        for (int i = 0; i < m; i++) {
            string t;
            TrieNode* cur = p.root;
            for (int j = 0; j < n; j++){
                if(cur->next[ans[j][i]-'a'] == nullptr)
                    return vector<bool>{false, false};
                cur = cur->next[ans[j][i]-'a'];
            }
            if(!(cur->isWord)) flag = false;
        }
        return vector<bool>{true, flag};
    }

    void dfs(int len) {
        if (maxlen * len <= maxarea) return;
        if (ans.size() >= maxlen) return;
        for (auto &x: len2string[len]) {
            ans.push_back(x);
            vector<bool> tmp = check(len);
            if (tmp[0]) {
                if (tmp[1]&&ans.size() * len > maxarea) {
                    maxarea = ans.size() * len;
                    finalAns = vector<string>(ans);
                }
                dfs(len);
            }

            ans.pop_back();
        }
    }
};

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class TrieNode {
public:
    TrieNode *next[26];
    bool isWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) next[i] = nullptr;
        isWord = false;
    }

//    ~TrieNode() {
//        for (int i = 0; i < 26; i++) delete next[i];
//    }
};

class Trie {
private:
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }

//    ~Trie() {
//        delete root;
//    }

    void insert(string word) {
        TrieNode *cur = root;
        for (auto &x: word) {
            if (cur->next[x - 'a'] == nullptr)
                cur->next[x - 'a'] = new TrieNode();
            cur = cur->next[x - 'a'];
        }
        cur->isWord = true;
    }

    bool search(string word) {
        TrieNode *cur = root;
        for (int i = 0; i < word.size() && cur; i++)
            cur = cur->next[word[i] - 'a'];
        return cur && cur->isWord;
    }

    bool startWith(string word) {
        TrieNode *cur = root;
        for (int i = 0; i < word.size() && cur; i++)
            cur = cur->next[word[i] - 'a'];
        return cur;
    }
};