Leetcode 212: Word Search II

June 13, 2017

Problem statement

Introduction

Trie is the kind of tree data structure and easy to save space with common prefix. Julia spent over 5 hours to work on one of trie algorithm and posted a code review on stackexchange.com called prefix neighbor. She went through the trie and learned that the trie can be in any form.

This time Julia had to relearn trie again. She had the weakness of data structure Trie, she could not figure out how to solve test case 36 and 37 two test cases timeout issue.

Code practice 

It is the hard level algorithm.

Julia worked on the Leetcode 212 word search.

Her first submission failed last 2 test cases from 36 - 37. Timeout issue. Julia did not know that she needs to use trie, she just used recursive function. The code is here.

Here is the C# code.

She studies the discussion written by a Googler - Yavinci, and wrote second practice. Still work on the code for more testing. Here is the C# code.

Julia continued to work on the trie and here is the C# code passing leetcode online judge.

Algorithm talk - learn Trie again

It is interesting to learn how data structure Trie to help solving timeout issues. For example, there are a lot of words like "aaaa", "aaab", "aaac", ...,"aaaz", Julia was so naive on June 13, 2017. She just goes over each word in the dictionary, and try to find each word using depth first search (DFS) recursive calls.

However the last 2 test case of 37 test cases time out. But Julia did not have idea how to solve it.

Julia needs to take a data structure coaching lesson again. so great to catch the opportunity.

As we can see, those words have same prefix "aaa", and the fourth char or last char is a to z. How to save the time to search, for example, if the path is the prefix of one word, then we need to continue to search.

Think about time complexity. My original solution (the C# code) is to go over each word, and then start to search board using DFS; so time complexity is related to how many words, each word is searched through board using DFS. If 26 words all starting from same prefix "aaa", then "aaa" will be searched in the board over 26 times.

The idea of using Trie, and then go over each element in the board, and then do DFS search against the Trie tree.

So preparation is the key, store all words to a prefix tree first.

Trie 

Plan to read Trie wiki article, review time complexity advantage of using Trie data strucutre.

A trie has a number of advantages over binary search tree. A trie can also be used to replace a hash table.

Topcoder using Trie - the article link is here.
Hackerearth tutorial about Trie - the article link is here.
Read 10 pages lecture notes about Trie - CMU lecture notes is here.