My cpp DFS solution, work out in VS2012 fail in oj[RTE]. Why?


  • 0
    L
    class Solution {
    public:
        bool exist(vector<vector<char> > &board, string word) {
            int rows = board.size();
            int cols = board[0].size();
            if (rows * cols < word.length()) return false;
            stack<int> start;
            // search for first char
            for (int i = 0; i < rows; i++) 
                for (int j = 0; j < cols; j++) {
                    if (board[i][j] == word.front()) 
                        start.push(i*rows + j);
                }
            while (start.size() > 0) { // search for each start point
                stack<int> dfs;
                dfs.push(start.top());
                start.pop();
                bool* visited = new bool[rows*cols];
                memset(visited, false, sizeof(bool)*rows*cols);
                visited[dfs.top()] = true;
                while (dfs.size() > 0) {
                    int s = dfs.top(); // get start point
                    int len = dfs.size(); // result string length
                    int check, i, j;
                    if (len == word.length()) return true;
                    // left
                    check = s-1;
                    i = check / cols;
                    j = check % cols;
                    if (check >= 0 && !visited[check] && board[i][j] == word[len]) {
                        visited[check] = true;
                        dfs.push(check);
                        continue;
                    }
                    // right
                    check = s+1;
                    i = check / cols;
                    j = check % cols;
                    if (check < cols*rows && !visited[check] && board[i][j] == word[len]) {
                        visited[check] = true;
                        dfs.push(check);
                        continue;
                    }
                    // up
                    check = s-cols;
                    i = check / cols;
                    j = check % cols;
                    if (check >= 0 && !visited[check] && board[i][j] == word[len]) {
                        visited[check] = true;
                        dfs.push(check);
                        continue;
                    }
                    // down
                    check = s+cols;
                    i = check / cols;
                    j = check % cols;
                    if (check < cols*rows && !visited[check] && board[i][j] == word[len]) {
                        visited[check] = true;
                        dfs.push(check);
                        continue;
                    }
    				if (dfs.size() == len) // there's no next char
    				    dfs.pop();
                }
            }
            return false;
        }
    };
    

    This code failed in test case:

    ["b","a","b","b","a"], "baa"

    Its idea is simple, check every adjacent point to see if there is a match character.

    The depth of stack dfs means the matched character number by now.

    And if there is no match character adjacent, dfs.pop() to go back to last point.

    I think this is straightforward and it worked out in my VS2012, but always got a RTE in oj.

    Thanks for any possible suggestions or hints.


Log in to reply
 

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