30ms AC with changing the value of board. (C++)


  • 1
    B

    I set the value of board[x][y] to '#' when it is used. In this way, I can save the memory to check whether board[x][y] is used.

    class Solution {
    public:
        void helper(vector<vector<char> > &board, string word, bool &res, int &m, int &n, int x, int y, int &k)
        {
            if (k == word.size())
            {
                res = true;
                return;
            }
            else
            {
                if (x > 0 && board[x - 1][y] == word[k])
                {
                    board[x - 1][y] = '#';
                    helper(board, word, res, m, n, x - 1, y, ++k);
                    if (res) return;//return early to save time
                    board[x - 1][y] = word[--k];//restore board.
                }
                if (x < m - 1 && board[x + 1][y] == word[k])
                {
                    board[x + 1][y] = '#';
                    helper(board, word, res, m, n, x + 1, y, ++k);
                    if (res) return;
                    board[x + 1][y] = word[--k];
                }
                if (y > 0 && board[x][y - 1] == word[k])
                {
                    board[x][y - 1] = '#';
                    helper(board, word, res, m, n, x, y - 1, ++k);
                    if (res) return;
                    board[x][y - 1] = word[--k];
                }
                if (y < n - 1 && board[x][y + 1] == word[k])
                {
                    board[x][y + 1] = '#';
                    helper(board, word, res, m, n, x, y + 1, ++k);
                    if (res) return;
                    board[x][y + 1] = word[--k];
                }
            }
            
        }
        bool exist(vector<vector<char> > &board, string word) {
            bool res = false;
            int x, y;
            
            int k = 0;
            int m = board.size(), n = board[0].size();
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (board[i][j] == word[k])
                    {
                        board[i][j] = '#';
                        helper(board, word, res, m, n, i, j, ++k);
                        if (res) return true;
                        board[i][j] = word[--k];
                    }
            return res;
        }
    };

  • 1
    P

    what if the word contains the char '#'?


  • 0
    B

    Thank you for your reminding very much. It is an issue when we extend this solution to more general problem. However, it's fine by this particular problem. The specification of "word search" is "The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once." I think the letter here doesn't take '#' into consideration. Anyway, thank you for your overall consideration.


  • 0
    P

    Yes, and replacing '#' with '\0' would be OK for the general cases :). And here is my code: https://leetcode.com/discuss/27445/my-19ms-accepted-c-code


Log in to reply
 

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