A Non-recursive Solution


  • 0
    B
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if(board.size() < 1 || board[0].size() < 1) return false;
            int rows = board.size(), cols = board[0].size(), len;
            vector<vector<bool>> buf(rows, vector<bool>(cols, false));
            int Dirs[4][2] ={{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 
            stack<pair<int, int>> steps;
            stack<int> dirs;
            for(int r = 0; r < rows; r ++) for (int c = 0; c < cols; c ++){
                if(board[r][c] != word[0]) continue;
                len = 1;
                buf[r][c] = true;
                steps.push(make_pair(r, c));
                dirs.push(-1);
                while(!steps.empty()){
                    if(len == word.length()) return true;
                    dirs.top() = dirs.top() + 1;
                    int curD = dirs.top();
                    pair<int, int> cur = steps.top();
                    if(dirs.top() >= 4){
                        buf[cur.first][cur.second] = false;
                        steps.pop();
                        dirs.pop();
                        len --;
                    }
                    else{
                        pair<int, int> nxt = make_pair(cur.first + Dirs[curD][0], cur.second + Dirs[curD][1]);
                        if(nxt.first < 0 || nxt.first >= rows || nxt.second < 0 || nxt.second >= cols) continue;
                        if(board[nxt.first][nxt.second] != word[len]) continue;
                        if(buf[nxt.first][nxt.second])continue;
                        len ++;
                        steps.push(nxt);
                        buf[nxt.first][nxt.second] = true;
                        dirs.push(-1);
                    }
                }
            }
            return false;
        }
    };
    

    But it costs more than 100 ms, much slower than recursive solution. Actually, this non-recursive solution just uses stacks to simulate a recursive solution.


Log in to reply
 

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