C# Nonrecursive DFS


  • 1
    H
    public bool Exist(char[,] board, string word) {
            int m = board.GetLength(0);
            int n = board.GetLength(1);
            
            int[] dx = new int[] { 1, -1, 0, 0 };
            int[] dy = new int[] { 0, 0, 1, -1 };
            
            for(int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i, j] != word[0]) continue;
                    
                    Stack<Tuple<int, int, int, HashSet<string>>> stack = new Stack<Tuple<int, int, int, HashSet<string>>>();
                    string pos = string.Format("{0},{1}", i, j);
                    stack.Push(new Tuple<int, int, int, HashSet<string>>(i, j, 0, new HashSet<string>() { pos }));
                    while(stack.Count > 0) {
                        Tuple<int, int, int, HashSet<string>> tp = stack.Pop();
                        int x = tp.Item1, y = tp.Item2, p = tp.Item3;
                        HashSet<string> path = tp.Item4;
                        
                        if ((p + 1) >= word.Length) return true;
                        
                        for(int k = 0; k < dx.Length; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            pos = string.Format("{0},{1}", nx, ny);
                            
                            if (nx < 0 || ny < 0 || nx >= m || ny >= n || board[nx, ny] != word[p + 1] || path.Contains(pos)) continue;
                            
                            HashSet<string> npath = new HashSet<string>(path);
                            npath.Add(pos);
                            stack.Push(new Tuple<int, int, int, HashSet<string>>(nx, ny, p + 1, npath));
                        }
                    }
                }
            }
            
            return false;
        }
    

Log in to reply
 

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