Share my solution without using Recursive, Solve memory exception


  • 0
    T
    public class Solution {
        public bool Exist(char[,] board, string word) {
            int rows = board.GetLength(0);
            int cols = board.GetLength(1);
            
            for(int i = 0;i<rows;i++){
                for(int j = 0;j<cols;j++){
                    if(Helper(board,word,i,j,rows,cols,word.Length))
                        return true;
                }
            }
            
            return false;
        }
        
        private bool Helper(char[,] board, string word,int i,int j,int rows,int cols,int len){
            if(board[i,j] != word[0])
                return false;
            var stack = new Stack<int>();
            var moveStack = new Stack<int>();
            
            int index = 0;
            stack.Push(i*cols+j);
            moveStack.Push(0);
            int[] xMove = new int[]{0,0,1,-1};
            int[] yMove = new int[]{1,-1,0,0};
            bool[,] visited = new bool[rows,cols];
            visited[i,j] = true;
            while(stack.Any() && stack.Count < len){
                var top = stack.Peek();
                int x = top/cols;
                int y = top%cols;
                if(moveStack.Peek() >= 4)
                {
                    stack.Pop();
                    moveStack.Pop();
                    visited[x,y] = false;
                    continue;
                }else{
                    var move = moveStack.Pop();
                    x+=xMove[move];
                    y+=yMove[move];
                    moveStack.Push(++move);
                    if(x<0 || x >= rows || y <0 || y >= cols || visited[x,y] || board[x,y] != word[stack.Count]){
                        continue;
                    }else{
                        stack.Push(x*cols+y);
                        moveStack.Push(0);
                        visited[x,y] = true;
                    }
                }
            }
            return stack.Count == len;
        }
    }
    

Log in to reply
 

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