My 44ms C++ solution


  • 1
    I

    If I coded this up with 'new' for each node, but never called 'delete', it would run in 48ms. But, once I added calls to delete (including a proper constructor and destructor in struct TrieNode), it swelled to 72ms.

    So, I rewound to the C way: Use calloc to get bulk zeroed memory cheaply, and then call free at the end. No constructors, no destructors. Just raw, pre-zeroed memory.

    The result is a glorious 44ms version. I preallocate a pool that's guaranteed to be large enough, but for many dictionaries will be oversized. Still, that little bit of slop translates into a lot of speed.

    class Solution {
        vector<string> results;
        int x_dim, y_dim;
    
        struct TrieNode {
            TrieNode* exits[26];
            bool      is_end;
        };
        
        void recurse( vector<vector<char>>& board, string& s, int x, int y, TrieNode* trie_curr ) {
            if ( unsigned(x) >= x_dim || unsigned(y) >= y_dim )
                return;
                
            const auto c = board[y][x];
            
            if ( !c )
                return;
          
            auto trie_next = trie_curr->exits[ c-'a' ];
            if ( !trie_next )
                return;
    
            s.push_back( c );
            board[y][x] = 0;
            
            if ( trie_next->is_end ) {
                results.push_back( s );
                trie_next->is_end = false;
            }
            
            recurse( board, s, x-1, y, trie_next );
            recurse( board, s, x+1, y, trie_next );
            recurse( board, s, x, y-1, trie_next );
            recurse( board, s, x, y+1, trie_next );
            
            board[y][x] = c;
            s.pop_back();
        }
        
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            if ( !words.size() || !board.size() || !board[0].size() ) 
                return results;
                
            int tot_chars = 0;
            for ( const auto& word : words ) 
                tot_chars += word.length();
                
            TrieNode* trie_pool = (TrieNode*)calloc( sizeof(TrieNode), tot_chars + 2 );
            int num_trie_nodes = 0;
            
            TrieNode* trie_root = &trie_pool[ num_trie_nodes++ ];
            
            for ( const auto& word : words ) {
                TrieNode* trie_curr = trie_root;
                for ( const auto c : word ) {
                    auto& trie_next = trie_curr->exits[ c-'a' ];
                    
                    if (!trie_next)
                        trie_next = &trie_pool[ num_trie_nodes++ ];
    
                    trie_curr = trie_next;
                }
                trie_curr->is_end = true;
            }  
    
            x_dim = board[0].size();
            y_dim = board.size();
    
            string s;
            for ( auto y = 0 ; y < y_dim ; ++y )
                for ( auto x = 0; x < x_dim; ++x )
                    recurse( board, s, x, y, trie_root );
            
            free( trie_pool );  // from C to shining C.
            return results;
        }
    };

  • 0
    P

    Very efficient code.

    I think one line should be

    TrieNode* pool=(TrieNode*)calloc(tot_chars+1,sizeof(TrieNode));

Log in to reply
 

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