fill cell each step backtracking + Trie


  • 1
    A

    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".
    we start with a square,

    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,1by '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     
    xxxx      xxxx     xxxx     xxxx     lxxx     lxxx     lxxx     laxx     laxx     ladx     lady    
    
    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;
        }
    };
    

  • 0

    @aaa45190 Same idea, java version


Log in to reply
 

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