CareerCup

Traverse the grid from left to right, top to bottom. For each cell, check if any words that start from this cell is in the dictionary. If current word is in the dictionary or the length of current word has exceeded the maximum length of words in dictionary, you can skip to next cell.
If the grid A has size N*M, dict has size K, the strings in dict has a maximum length of L, then the time complexity will be
O(NM(min(max(N, M), L) + log K))

@wyu277 It will be great if you can provide a small example.

With more time than a standard Interview, I would expect a much better algorithm than this:

Pseudo code:
starting function:
create trie from valid strings
for each column i in char[][]
for each row j in char[][]
execute a DFS starting at char[i][j]
}
}

DFS (i, j):
if i or j are invalid indices in char[][]
return
add position i, j to the working array
if working array is a completed word in the trie
add working array to results
if working array is within the trie
set position i, j as having been explored
DFS(i-1, j)
DFS(i, j-1)
DFS(i+1, j)
DFS(i, j+1)
unset position i,j as having been explored
remove position(i, j) from the working array

Complexity for this solution really stinks. And it will operate at roughly O(n^2*m^2) where n and m are the dimensions of the char[][].

Code:

static class TrieNode{
	boolean isWord;
	HashMap<Character, TrieNode> nodes = new HashMap<Character, TrieNode>();
}

public static ArrayList<String> getWords(char[][] grid, List<String> words){
	TrieNode trie = buildTrie(words);
	ArrayList<String> results = new ArrayList<String>();
	for(int i = 0; i < grid.length; i++){
		for(int j = 0; j < grid[0].length; j++){
			dfs(grid, i, j, trie, results);
		}
	}
	return results;
}

private static void dfs(char[][] grid, int i, int j, TrieNode trie, ArrayList<String> results){
	ArrayList<Character> working = new ArrayList<Character>();
	boolean[][] charUsed = new boolean[grid.length][grid[0].length];
	dfsRecur(grid, i, j, working, charUsed, trie, results);
}

private static void dfsRecur(char[][] grid, int i, int j, ArrayList<Character> working, boolean[][] charUsed, TrieNode trie, ArrayList<String> results){
	if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || charUsed[i][j]){
		return;
	}
	char c = grid[i][j];
	TrieNode nextNode = trie.nodes.get(c);
	if(nextNode != null){
		working.add(c);
		if(nextNode.isWord){
			char[] wordArr = new char[working.size()];
			for(int i = 0; i < wordArr.length; i++){
				wordArr[i] = working.get(i);
			}
			results.add(new String(wordArr));
		}
		charUsed[i][j] = true;
		dfsRecur(grid, i-1, j, working, charUsed, nextNode, results);
		dfsRecur(grid, i, j-1, working, charUsed, nextNode, results);
		dfsRecur(grid, i+1, j, working, charUsed, nextNode, results);
		dfsRecur(grid, i, j+1, working, charUsed, nextNode, results);
		charUsed[i][j] = false;
	}
}

private static TrieNode buildTrie(List<String> words){
	TrieNode root = new TrieNode();
	TrieNode node = null;
	for(String str : words){
		node = root;
		int index = 0;
		char[] arr = word.getChars();
		for(int i = 0; i < arr.length; i++){
			char c = arr[i];
			TrieNode nextNode = node.nodes.get(c);
			if(nextNode == null){
				nextNode = new TrieNode();
				node.nodes.put(c, nextNode);
			}
			node = nextNode;
		}
		node.isWord = true;
	}
	return root;
}

var dic = ["car", "add", "rum", "rap", "carrots", "addition"];
var matrix = [['c','a','r'], ['o','d','u'],['s','d','m']];

function Node (value) {

	var self = this;
	self.value = value;
	self.children = {};
	self.isWord = false;
}
function Trie () {

	var self = this;
	self.children = {};
	self.create = function (dic) {

		var trie = self;
		for (var i=0; i<dic.length; i++) {

			var word = dic[i];
			var t = trie;
			for (var j=0; j<word.length; j++) {

				var ch = word[j];
				if (t.children[ch] === undefined) {
					t.children[ch] = new Node(ch);
				}
				t = t.children[ch];
			}
			t.isWord = true;
		}
	}
}

(function searchAllPossibleWords(matrix, dic) {

	// Create trie tree in o(PxK) where p is the number of dictionary entries and K is the max size of
	// a dictionary entry. (Is this running time correct)?
	var trie = new Trie();
	trie.create(dic);

	// This could be broken down into a utility function for recursion usage
	var wordFound = "";
	var t = null;
	var ch = null;

	// for each row. Running time is O(RxC) R is # of rows and C is number of columns.
	for (var r=0; r<matrix.length; r++) {

		wordFound = "";
		t = trie;
		for (var c=0; c<matrix[r].length; c++) {

			ch = matrix[r][c];
			if (t.children[ch] === undefined) {
				break;
			}
			wordFound += ch;
			t = t.children[ch];
		}
		if (t.isWord === true) {
			console.log("found word: " + wordFound);
			wordFound = "";
		}
	}

	// for each column. Running time is O(CxR) C is # of columns and R is # of rows
	for (var c=0; c<matrix[0].length; c++) {

		wordFound = "";
		t = trie;
		for (var r=0; r<matrix.length; r++) {

			ch = matrix[r][c];
			if (t.children[ch] === undefined) {
				break;
			}
			wordFound += ch;
			t = t.children[ch];
		}
		if (t.isWord === true) {
			console.log("found word: " + wordFound);
			wordFound = "";
		}
	}

})(matrix, dic);

Are my running times correct? What you guys think...