提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

[LeetCode] Word Search

LeetCode word search
2023-09-11 14:17:25 时间

Given a 2D board and a word, find if the word exists in the grid.

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.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 

 

Hide Tags
 Array Backtracking
 
 
思路一：dfs，但是 Time Limit Exceeded
class Solution {
        vector<vector<bool> > canUse;
    public:
        bool dfs(int dep, int x, int y, vector<vector<char> >& board, string& word)
        {
            if(dep == word.size())
                return true;

            int row = board.size();
            int col = board[0].size();
            if(x < 0 || x >= row ||
                y <0 || y >= col )
                return false;

            if(board[x][y] != word[dep])
                return false;

            //mark
            canUse[x][y] = false;


            if(x < row-1 && canUse[x+1][y] )
            {
                if(dfs(dep+1, x+1, y, board, word))
                {
                    //mark
                    canUse[x][y] = true;
                    return true;
                }
            }

            if(x >0 && canUse[x-1][y] )
            {
                if(dfs(dep+1, x-1, y, board, word))
                {
                    //mark
                    canUse[x][y] = true;
                    return true;
                }
            }

            if(y < col-1 && canUse[x][y+1])
            {
                if(dfs(dep+1, x, y+1, board, word))
                {
                    //mark
                    canUse[x][y] = true;
                    return true;
                }
            }
            if(y >0 && canUse[x][y-1])
            {
                if(dfs(dep+1, x, y-1, board, word))
                {
                    //mark
                    canUse[x][y] = true;
                    return true;
                }
            }

            canUse[x][y] = true;

            return false;

        }

        bool exist(vector<vector<char> > &board, string word)
        {
            int row = board.size();
            if(row == 0) return false;
            int col = board[0].size();
            
            if(word.size() > row*col) return false;

            canUse.clear();
            vector<bool> tmp(col, true);
            canUse.resize(row, tmp);

            for(int i = 0; i< row; i++)
            {
                for(int j = 0; j< col; j++)
                {
                    if(dfs(0, i, j, board, word ))
                        return true;
                }
            }
            return false;
        }
};

 

参考了https://github.com/soulmachine/leetcode 感觉也差不多，貌似少了一些边界条件判断，就AC了

 不同之处用红色标注了，且x y 的越界也不需要判断了。。

class Solution {
        vector<vector<bool> > canUse;
    public:
        bool dfs(int dep, int x, int y, vector<vector<char> >& board, string& word)
        {
            if(dep == word.size())
                return true;

            int row = board.size();
            int col = board[0].size();
            if(x < 0 || x >= row ||
                y <0 || y >= col )
                return false;

            if(canUse[x][y] == false)
                return false;

            if(board[x][y] != word[dep])
                return false;

            //mark
            canUse[x][y] = false;

            bool retVal = dfs(dep+1, x+1, y, board, word) ||
                dfs(dep+1, x-1, y, board, word) ||
                dfs(dep+1, x, y+1, board, word) ||
                dfs(dep+1, x, y-1, board, word);

            //mark
            canUse[x][y] = true;

            return retVal;
        }

        bool exist(vector<vector<char> > &board, string word)
        {
            int row = board.size();
            if(row == 0) return false;
            int col = board[0].size();

            canUse.clear();
            vector<bool> tmp(col, true);
            canUse.resize(row, tmp);

            for(int i = 0; i< row; i++)
            {
                for(int j = 0; j< col; j++)
                {
                    if(dfs(0, i, j, board, word ))
                        return true;
                }
            }
            return false;
        }
};

 

 

相关文章