Max Words Package

Max Words Package

You are given a NxN matrix composed of lowercase letters and a list of words. Your task is to find out the largest list of words that can be formed by the letters in the matrix.

Constraints:

  • each letter can only be used once for a word;
  • once the cell (letter) in the matrix is taken by a word, then the other words in the same list cannot use that cell again.

Example:
Input:
{
{‘o’, ‘a’, ‘a’, ‘n’},
{‘e’, ‘t’, ‘a’, ‘e’},
{‘i’, ‘h’, ‘k’, ‘r’},
{‘i’, ‘f’, ‘l’, ‘v’}
}
{“eat”, “oath”, “aak”, “ner”, “oei”, “thfl”}
Output:
{“oei”, “ner”, “aak”, “thfl”}
Explanation:
Actually all these words can be formed in the matrix, but we have to ensure the biggest list of words.

  • if we take “eat”, then the list should be {“eat”, “oei”};
  • if we take “oath”, then the list should be {“oath”, “aak”, “ner”};
  • if we take “aak”, then the list should be {“oei”, “aak”, “ner”, “thfl”};
    So we should return the biggest list {“oei”, “aak”, “ner”, “thfl”} as the final result.

Solution

Clearly since there are lots of words we need to search in the matrix, we should take advantage of the Trie Tree to avoid redundant checking for words with the same prefix. So let’s just hit the road:

  • build the Trie Tree based on the list of the words provided;
  • start the search from each possible cell in the matrix and do backtracking: as soon as we take that cell, we label it and after the further searching, we un-label it for other searching paths;
    There will be two directions in the searching:
  1. if the current node indicate a complete word then we collect the word and try to start another word searching from the root of the TreeTrie again and try each possible unlabelled cell; and in each try, we collect the bigger valid result to update the current container;
  2. if the current node does not indicate a word, then we try the other four different directions around the current cell and also collect the valid results and update the current container.

Note the corner cases:

  1. out of range
  2. labelled cell
  3. invalid node
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
#include <iostream>
#include <vector>
using namespace std;
typedef struct TrieTree{
bool isWord{false};
TrieTree *children[26];
TrieTree(){
fill_n(children, 26, nullptr);
}
} TrieTree;
TrieTree* buildTrieTree(const vector<string>& words){
TrieTree *root = new TrieTree(), *cur = NULL;
for(const auto& w: words){
cur = root;
for(auto c: w){
if(!cur->children[c-'a']) cur->children[c-'a'] = new TrieTree();
cur = cur->children[c-'a'];
}
cur->isWord = true;
}
return root;
}
void searchWords(TrieTree* root, string path, vector<string>& v){
if(!root) return ;
if(root->isWord) v.push_back(path);
for(int i = 0; i < 26; ++i){
if(!root->children[i]) continue;
searchWords(root->children[i], path+char(i+'a'), v);
}
}
void printV(const vector<string>& v){
for(const auto& w: v) cout<<w<<",";
cout<<endl;
}
void traverse(TrieTree* root, TrieTree* node, int r, int c, vector<vector<char>>& matrix,
string path, vector<string>& v){
int size = matrix.size();
if(r==-1 || c==-1 || r==size || c==size || matrix[r][c]=='#') return;
char a = matrix[r][c];
node = node->children[a-'a'];
if(!node) return;
matrix[r][c] = '#';
path += a;
if(node->isWord) {
v.push_back(path);
vector<string> maxRet = v;
for(int r = 0; r < size; ++r){
for(int c = 0; c < size; ++c){
vector<string> v0 = v;
traverse(root, root, r, c, matrix, "", v0);
if(v0.size() > maxRet.size()) maxRet = v0;
}
}
v = maxRet;
}
else {
vector<string> v0(v), v1(v), v2(v), v3(v), t = v;
traverse(root, node, r-1, c, matrix, path, v0);
if(v0.size() > t.size()) t = v0;
traverse(root, node, r, c-1, matrix, path, v1);
if(v1.size() > t.size()) t = v1;
traverse(root, node, r+1, c, matrix, path, v2);
if(v2.size() > t.size()) t = v2;
traverse(root, node, r, c+1, matrix, path, v3);
if(v3.size() > t.size()) t = v3;
v = t;
}
matrix[r][c] = a;
}
int main(int argc, char *argv[])
{
int size = 4;
vector<vector<char>> matrix{
{'o', 'a', 'a', 'n'},
{'e', 't', 'a', 'e'},
{'i', 'h', 'k', 'r'},
{'i', 'f', 'l', 'v'}
};
vector<string> words{"eat", "oath", "aak", "ner", "oei"};
TrieTree *root = buildTrieTree(words);
vector<string> ret;
for(int r = 0; r < size; ++r){
for(int c = 0; c < size; ++c){
vector<string> v;
traverse(root, root, r, c, matrix, "", v);
if(v.size() > ret.size()) ret = v;
}
}
for(auto w: ret) cout<<w<<endl;
return 0;
}

Always welcome new ideas and practical tricks, just leave them in the comments!