Share my C++ code clear but time comsuming


  • 0
    L
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) 
        {
            if(word.empty())return 1;
            if(board.empty())return 0;
            vector<pair<int,int>> stack;
            set<pair<int,int>> exist;
            pair<int,int> pos(0,0);
            for(int i=0;i<board.size();i++)//find the first match
            {
                for(int j=0;j<board[0].size();j++)
                if(word[0]==board[i][j])
                stack.push_back(make_pair(i,j));
            }
            for(int i=0;i<stack.size();i++)
            {
                exist.insert(stack[i]);
              if(exist1(board, word, 1,exist, stack[i]))return 1;
                exist.erase(stack[i]);
            }
            return 0;
           
        }
    private:
         bool search(vector<vector<char>>& board,pair<int,int>pos,char target,vector<pair<int,int>>&stack,set<pair<int,int>> &exist)
         {
             bool ret=0;
            if(pos.first!=0)                //up
            {
                if(board[pos.first-1][pos.second]==target&&!exist.count(make_pair(pos.first-1,pos.second)))
                {stack.push_back(make_pair(pos.first-1,pos.second));
                ret=1;}
            }
            if(pos.first!=board.size()-1)                //down
            {
                if(board[pos.first+1][pos.second]==target&&!exist.count(make_pair(pos.first+1,pos.second)))
                {stack.push_back(make_pair(pos.first+1,pos.second));
                ret=1;}
            }
            if(pos.second!=0)                //left
            {
                if(board[pos.first][pos.second-1]==target&&!exist.count(make_pair(pos.first,pos.second-1)))
                {stack.push_back(make_pair(pos.first,pos.second-1));
                ret=1;}
            }
            
            if(pos.second!=board[0].size()-1)                //right
            {
                if(board[pos.first][pos.second+1]==target&&!exist.count(make_pair(pos.first,pos.second+1)))
                {stack.push_back(make_pair(pos.first,pos.second+1));
                ret=1;}
            }
            return ret;
             
             
         }
         
          bool exist1(vector<vector<char>>& board, string word,int index,set<pair<int,int>> &exist,pair<int,int> pos) 
        {
            if(index>=word.size())return 1;
            vector<pair<int,int>> start;
            search(board,pos,word[index],start,exist);
            if(start.empty()) return 0;
            if(index==word.size()-1)return 1;
            for(int i=0;i<start.size();i++)
            {
                exist.insert(start[i]);
                if(exist1(board, word, index+1,exist, start[i]))return 1;
                exist.erase(start[i]);
            }
            return 0; 
        }
    };

Log in to reply
 

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