# fill cell each step backtracking + Trie

• here is my idea:
key idea each time fill a cell, then find the next empty cell and check if it can be filled by some letter.
but I need an extra vector to record the current cell's address in the Trie
steps:
suppose the word length is 4 and the words are `["area","lead","wall","lady","ball"]`
then one of the result is `"wall","area","lead","lady"`.

1. fill the cell with index `0, 0` and say w fill it with `'w'`, then the next cell's index is `0,1`
2. fill the cell with index `0,1`by `'a'`, then next cell is `0,2`
3. fill the cell `0, 2` by `'l'` and continue do that

the below is a picture:

``````xxxx      wxxx     waxx     walx     wall     wall     wall     wall     wall     wall     wall
xxxx      xxxx     axxx     axxx     axxx     arxx     arex     area     area     area     area
xxxx  ->  xxxx ->  xxxx ->  lxxx ->  lxxx ->  lxxx ->  lexx  -> lexx  -> leax  -> lead ->  lead
``````
``````class Solution {
struct TrieNode{
TrieNode* children[26];
bool isword;
TrieNode(){
isword = false;
memset(children, 0, sizeof(children));
}
};
public:
TrieNode* buildTrie(vector<string>& words){
TrieNode* root = new TrieNode();
for(string word : words){
TrieNode* node = root;
for(char c : word){
int index = c - 'a';
if(node->children[index] == NULL)
node->children[index] = new TrieNode();
node = node->children[index];
}
node->isword = true;
}
return root;
}

void wordSquares(int oi, int oj, int size, vector<string>& res, vector<vector<string>>& result, vector<TrieNode*> nodes){
if(oi == size){
result.push_back(res);
return;
}

int nj = (oj+1)%size;
int ni = oi + (oj+1)/size;

//get next empty cell but need to jump over the diagonal cell, here the diagonal cell I mean the cell has the index  oj,oi
while(ni != size && (res[ni][nj] != '#' || (ni == oj && nj == oi))){
nj++;
ni += nj/size;
nj %= size;
}
TrieNode* first = nodes[oi];
TrieNode* second = nodes[oj];

for(int i=0; i<26; i++){
if(first->children[i] != NULL && second->children[i] != NULL ){
char c = i + 'a';
res[oi][oj] = c;
res[oj][oi] = c;
nodes[oi] = first->children[i];
nodes[oj] = second->children[i];
wordSquares(ni, nj, size, res, result, nodes);
}
}
nodes[oi] = first;
nodes[oj] = second;
res[oi][oj] = '#';
res[oj][oi] = '#';
}

vector<vector<string>> wordSquares(vector<string>& words) {
TrieNode* root = buildTrie(words);
vector<vector<string>> result;
int size = words.size()==0? 0 : words.front().size();
vector<string> res(size, string(size, '#'));
vector<TrieNode*> nodes(size, root); // using to record the current cell's address in Trie
wordSquares(0, 0, size, res, result, nodes);
return result;
}
};
``````

• @aaa45190 Same idea, java version

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.