Help!Time Limit Exceeded Last executed input: ["aaaa","aaaa","aaaa","aaaa","aaab"], "aaaaaaaaaaaaaaaaaaaa"


  • 0
    V
    class Solution {
        private:
            struct node{
                int i;
                int j;
                string goal_string;
                map<string,bool> path;
            };
        public:
            string itoa(int a){
                char ch[10];
                sprintf(ch,"%d",a);
                string result(ch);
                return result;
            }
            bool exist(vector<vector<char> > &board, string word) {
                int row=board.size();
                if(row==0){
                    return false;
                }
                int colum=board[0].size();
                if(colum==0){
                    return false;
                }
                int word_length=word.size();
                if(word_length==0){
                    return false;
                }
                stack<node> node_stack;
                for(int i=0;i<row;++i){
                    for(int j=0;j<colum;++j){
                        if(board[i][j]==word[0]){
                            map<string,bool> temp_map;
                            string temp_s="";
                            temp_s=itoa(i)+temp_s+",";
                            temp_s+=itoa(j);
                            temp_map[temp_s]=true;
                            node temp_node={i,j,word,temp_map};
                            node_stack.push(temp_node);
                            while(!node_stack.empty()){
                                if(node_stack.top().goal_string.size()==1){
                                    return true;
                                }
                                temp_node=node_stack.top();
                                node_stack.pop();
                                temp_s=temp_node.goal_string.substr(1);
                                temp_map=temp_node.path;
                                string ks="";
                                if(temp_node.i-1>=0&&board[temp_node.i-1][temp_node.j]==temp_s[0]&&temp_map.find(ks+itoa(temp_node.i-1)+","+itoa(temp_node.j))==temp_map.end()){
                                    map<string,bool> nimei=temp_map;
                                    nimei[ks+itoa(temp_node.i-1)+","+itoa(temp_node.j)]=true;
                                    node cao={temp_node.i-1,temp_node.j,temp_s,nimei};
                                    node_stack.push(cao);
                                }
                                if(temp_node.i+1<row&&board[temp_node.i+1][temp_node.j]==temp_s[0]&&temp_map.find(ks+itoa(temp_node.i+1)+","+itoa(temp_node.j))==temp_map.end()){
                                    map<string,bool> nimei=temp_map;
                                    nimei[ks+itoa(temp_node.i+1)+","+itoa(temp_node.j)]=true;
                                    node cao={temp_node.i+1,temp_node.j,temp_s,nimei};
                                    node_stack.push(cao);
                                }
                                if(temp_node.j-1>=0&&board[temp_node.i][temp_node.j-1]==temp_s[0]&&temp_map.find(ks+itoa(temp_node.i)+","+itoa(temp_node.j-1))==temp_map.end()){
                                    map<string,bool> nimei=temp_map;
                                    nimei[ks+itoa(temp_node.i)+","+itoa(temp_node.j-1)]=true;
                                    node cao={temp_node.i,temp_node.j-1,temp_s,nimei};
                                    node_stack.push(cao);
                                }
                                if(temp_node.j+1<colum&&board[temp_node.i][temp_node.j+1]==temp_s[0]&&temp_map.find(ks+itoa(temp_node.i)+","+itoa(temp_node.j+1))==temp_map.end()){
                                    map<string,bool> nimei=temp_map;
                                    nimei[ks+itoa(temp_node.i)+","+itoa(temp_node.j+1)]=true;
                                    node cao={temp_node.i,temp_node.j+1,temp_s,nimei};
                                    node_stack.push(cao);
                                }
                            }
                        }
                    }
                }
                return false;
            }
    };
    

    who can help me find out why this codes meet time-limit-exceeded problem,it run fast in local but TLE by OJ,I'm almost mat about this~!!


  • 0
    V

    I have find the reason.because of the map, the type of map slow down the speed ,so I change a method without map , and it passed.


Log in to reply
 

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