C# TrieNode + DFS backtracking Solution


  • 0
    L

    The fastest OJ run time so far -- 520ms. No need to build all Trie class but only add/search feature.

    private class TrieNode{
        public TrieNode[] Next {get;set;}
        public bool EOW {get;set;}
        public TrieNode() { EOW = false; Next = new TrieNode[26]; }
    }
    public IList<string> FindWords(char[,] board, string[] words) {
        TrieNode root = new TrieNode();
        for(int i = 0; i < words.Length; i++){
            TrieNode cur = root;
            for(int j = 0; j < words[i].Length; j++){
                if(cur.Next[words[i][j] - 'a'] == null)
                    cur.Next[words[i][j] - 'a'] = new TrieNode();
                cur = cur.Next[words[i][j] - 'a'];
            }
            cur.EOW = true;
        }
        ISet<string> result = new HashSet<string>();
        for(int i = 0; i < board.GetLength(0); i++)
            for(int j = 0; j < board.GetLength(1); j++)
                dfsSearch(board, i, j, root.Next[board[i, j] - 'a'], new StringBuilder().Append(board[i, j]), result);
        return result.ToList();
    }
    private void dfsSearch(char[,] board, int X, int Y, TrieNode curNode, StringBuilder curStr, ISet<string> result){
        if(curNode == null) return;
        if(curNode.EOW) result.Add(curStr.ToString());
        char tmp = board[X, Y];
        board[X, Y] = '0';
        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++){
                if(Math.Abs(i + j) != 1) continue;
                if(X + i < 0 || X + i >= board.GetLength(0)) continue;
                if(Y + j < 0 || Y + j >= board.GetLength(1)) continue;
                if(board[X + i, Y + j] == '0') continue;
                dfsSearch(board, X + i, Y + j, curNode.Next[board[X + i, Y + j] - 'a'], curStr.Append(board[X + i, Y + j]), result);
                curStr.Length = curStr.Length - 1;
            }
        board[X, Y] = tmp;
    }

Log in to reply
 

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