First version of word search problem.

The  idea is to do dfs on every node, until the word is found in the array. Assume the time complexity of a single dfs is O(mn) where n and m are the #row,#column, respectively, the overall time complexity should go up to O(m^2 n^2). 

Doubt if this is the tight upper-bound, it really depends on the position of the first 'non-match'character, so that each dfs will return before traverses all elements in the array. One of the  worst scenario I can think of:

search 'aaaaaaaaa' in [aaa,aaa,aab] , in a left, up, right, bottom order
First version of valid parentheses problem. 

Extension: what if the number of parentheses types are not limited to three? A more general approach? Unicode?