Fully commented C++ solution using a Trie, inspired by @StefanPochmann


  • 1
    G
    class Solution {
    public:
        
        vector<string> W;
        vector<vector<string> > Squares;
        vector<string> Square;
        
        struct TrieNode
        {
            vector<string> Words;
            vector<TrieNode*> Nodes;
            
            TrieNode()
            :
            Nodes(26,NULL)
            {
            }
            
        } *Root = new TrieNode;
        
        
        //
        // Given the Root of the Trie add the string Str
        // character by Character.
        // For each node we visit on our way, we store the
        // entire string in that node.
        // this will allow us to access it quickly when 
        // we search for prefixes of this word
        //
        
        void AddWord(TrieNode *R, const string &Str)
        {
            if(Str.empty())
            {
                return;    
            }
            
            R->Words.push_back(Str);
            
            for(auto &c : Str)
            {
                if(R->Nodes[c - 'a'] == NULL)
                {
                  R->Nodes[c - 'a'] = new TrieNode;
                }
                
                R = R->Nodes[c - 'a'];
                R->Words.push_back(Str);
            }
        }
        
        //
        // Return all words that correspond to the prefix 
        // Str
        //
        vector<string> FindAll(TrieNode *R, const string &Str)
        {
            if(Str.empty())
            {
                return R->Words;
            }
            
            if(R == NULL || R->Nodes[Str[0] - 'a'] == NULL)
            {
                return vector<string>();
            }
            
            return FindAll(R->Nodes[Str[0] - 'a'],Str.substr(1));
        }
    
        
        //
        // The main recursive function
        // receives an index i which indicates
        // the row in the square to be filled
        //
        void FillSquares(int i)
        {
            //
            // when i is equal to the maximum number
            // of rows in the square (size of a word)
            // insert the Square into the vector<> Squares
            //
            
            if(i == W[0].size())
            {
                if(Square.size() == W[0].size())
                {
                    Squares.push_back(Square);
                }
                
                return;
            }
            
            //
            // The prefix is based on the the i'th column of the square
            // We need to only take the k < i letters from this column
            //
            
            string Prefix;
            
            for(int k = 0; k < i; ++k)
            {
                Prefix.push_back(Square[k][i]);    
            }
            
            //
            // FindAll will return all words that correspond 
            // to this prefix, and will try them all
            //
            
            for(auto &w : FindAll(Root,Prefix))
            {
                Square.push_back(w);
                FillSquares(i + 1);
                Square.pop_back();
            }
        }
        
        vector<vector<string> > wordSquares(vector<string>& words)
        {
            W = words;
            
            for(auto &w : words)
            {
                AddWord(Root,w);
            }
            
            FillSquares(0);
            
            return Squares;
        }
    };

Log in to reply
 

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