# My 44ms C++ solution

• 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;
}
};``````

• Very efficient code.

I think one line should be

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

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