You are using an outdated browser. Please update your browser for a better user experience.

Word Search

string

Given an m x n board of characters and a list of string words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word

Example 1:

This problem is most effectively done using the trie data structure. We us trie strucutre to store words then, for each character in the board, we can use backtracking to search whether we can construct a word starting from this character.