Why it has no output?


  • 0
    W

    This code runs for every case on my local computer. But it keeps saying:

    Submission Result: Wrong Answer
    Input: "hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
    Output: []
    Expected: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

    The above example runs without any problem and output the correct result. I have no idea why it gives no output at the OJ end.

    After playing with the SIZE=5000, i guess I even pass the "nanny" "...." example. Cuz when I set size to about 4000, it's a runtime error on that example.

       struct NODE{
        	int pos;
        	vector<int> path;
        };
        
        
    class Solution {
    public:
    	static const int SIZE = 5000;
    	vector<int> count[SIZE];
    	vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
    		vector<vector<string>> result;		
    		vector<string> input;
    		for(auto i1=dict.begin(); i1!=dict.end(); i1++){
    			input.push_back(*i1);
    		}
    
    		int i,j;
    		int length = input.size();
    		count[0].push_back(0);
    		count[length+1].push_back(Distance(start, end));
    		for(i=0; i<length;i++)
    			count[length+1].push_back(Distance(end, input[i]));
    		count[length+1].push_back(0);
    
    
    		int step[SIZE];
    		for(i=0; i<SIZE; i++)
    			step[i] = length+5;
    		queue<NODE> q;
    		length = length+1;
    		NODE head;
    		head.pos = length;
    		head.path.push_back(length);
    		q.push(head);
    		head.pos = -1; //delimit
    		q.push(head);
    		int minstep = 1;
    		step[length] = 1;
    		bool findatleastone = false;
    		while(q.empty() == false){
    			NODE cur = q.front();
    			q.pop();
    			if(cur.pos == -1){
    				if(q.size() == 0) //no result
    					break;
    				if(findatleastone == true)
    					break;
    				q.push(cur); //another delimit
    				minstep++;
    			}else{
    				for(i=0; i<cur.pos; i++){
    					if(count[cur.pos].size() == 0)
    						ComputeOnDemend(count, cur.pos, start, end, input);
    					if(count[cur.pos][i] == 1 && step[i] >= minstep){
    						NODE tmp = cur;
    						tmp.pos = i;
    						tmp.path.push_back(i);
    						q.push(tmp);
    						step[i] = minstep;
    						if(i==0){
    							findatleastone = true;
    							AddSolution(result, tmp, input, start, end);
    						}
    					}
    				}
    			}
    		}
    		return result;
    	}
    
    	void ComputeOnDemend(vector<int> *count, int pos, string &start, string &end, vector<string> &input)
    	{
    		int i=0;
    		count[pos].push_back(Distance(start, input[pos-1]));
    		for(i=0; i<pos; i++)
    			count[pos].push_back(Distance(input[pos-1], input[i]));
    		count[pos].push_back(0);
    
    	}
    	int Distance(string a, string b){
    		int num = 0;
    		for(int i=0; i<a.size(); i++)
    			if(a[i] != b[i])
    				num++;
    		return num;
    	}
    	void AddSolution(vector<vector<string>> &result, NODE &tmp, vector<string> &input, string &start, string &end)
    	{
    		int size = tmp.path.size();
    		vector<string> sol;
    		sol.push_back(start);
    		for(int i=size-2; i>0; i--){
    			sol.push_back( input[tmp.path[i]-1]);
    		}
    		sol.push_back(end);
    		result.push_back(sol);
    	}
    };

Log in to reply
 

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