Leetcode 212. 单词搜索 II（DAY 114) ---- 回溯算法学习期

本文主要是介绍Leetcode 212. 单词搜索 II（DAY 114) ---- 回溯算法学习期，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • 原题题目
  • 代码实现（首刷TLE 39\40）
  • 代码实现（首刷自解优化 双超80）

原题题目

代码实现（首刷TLE 39\40）

class Solution {
public:
    bool backtracking(const vector<vector<char>>& board,vector<vector<bool>>& visit,vector<string>& ret,const string& word,int pos,int x,int y)
    {
        if(x<0 || x>=board.size() || y<0 || y>= board[0].size() || word[pos] != board[x][y] || visit[x][y])    return false;

        if(pos == word.size()-1)
        {
            ret.emplace_back(word);
            return true;
        }

        int flag = 0;
        visit[x][y] = true;        
        if(backtracking(board,visit,ret,word,pos+1,x+1,y) || backtracking(board,visit,ret,word,pos+1,x-1,y) || backtracking(board,visit,ret,word,pos+1,x,y+1) || backtracking(board,visit,ret,word,pos+1,x,y-1))
            flag = 1;
        visit[x][y] = false;
        if(flag)    return true;
        else    return false;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<vector<bool>> visit(board.size(),vector<bool>(board[0].size(),false));
        vector<string> ret;
        int count = 0;
        vector<bool> wordjudge(words.size(),false);

        for(int i=0;i<board.size();++i)
        {
            for(int j=0;j<board[0].size();++j)
            {
                for(int k=0;k<wordjudge.size();++k)
                {
                    int flag = 0;
                    if(wordjudge[k] || board[i][j] != words[k][0])  continue;
                    if(backtracking(board,visit,ret,words[k],0,i,j))
                    {
                        ++count;
                        wordjudge[k] = true;   
                    }
                }
                if(count == wordjudge.size())   return ret;
            }
        }

        return ret;
    }
};

代码实现（首刷自解优化 双超80）

class Solution {
public:
    bool backtracking(const vector<vector<char>>& board,vector<vector<bool>>& visit,vector<string>& ret,const string& word,int pos,int x,int y)
    {
        if(x<0 || x>=board.size() || y<0 || y>= board[0].size() || word[pos] != board[x][y] || visit[x][y])    return false;

        if(pos == word.size()-1)
        {
            ret.emplace_back(word);
            return true;
        }

        int flag = 0;
        visit[x][y] = true;        
        if(backtracking(board,visit,ret,word,pos+1,x+1,y) || backtracking(board,visit,ret,word,pos+1,x-1,y) || backtracking(board,visit,ret,word,pos+1,x,y+1) || backtracking(board,visit,ret,word,pos+1,x,y-1))
            flag = 1;
        visit[x][y] = false;
        if(flag)    return true;
        else    return false;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<vector<bool>> visit(board.size(),vector<bool>(board[0].size(),false));
        vector<string> ret,temp;
        unordered_set<char> set;
        int count = 0;
        for(const auto& row:board)
            for(const auto& chr:row)
                set.emplace(chr);

        for(const auto& word:words)
        {
            int flag = 0;
            for(const auto& chr:word)
            {
                if(set.find(chr) != set.end())  continue;
                flag = 1;
                break;
            }
            if(!flag)   temp.emplace_back(word); 
        }

        words = temp;
        vector<bool> wordjudge(words.size(),false);
        for(int i=0;i<board.size();++i)
        {
            for(int j=0;j<board[0].size();++j)
            {
                for(int k=0;k<wordjudge.size();++k)
                {
                    int flag = 0;
                    if(wordjudge[k] || board[i][j] != words[k][0])  continue;
                    if(backtracking(board,visit,ret,words[k],0,i,j))
                    {
                        ++count;
                        wordjudge[k] = true;   
                    }
                }
                if(count == wordjudge.size())   return ret;
            }
        }

        return ret;
    }
};

这篇关于Leetcode 212. 单词搜索 II（DAY 114) ---- 回溯算法学习期的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！