Why did I get a TLE using C++ but get an accepted by using Java with the same method???any mistakes?


  • 0
    Z

    what the differences between these two versions may be just the language, what the hell did i get two different replies?It costed me a large amount of time to find the mistakes in C ++ algorithm. I also found those accepted answers in discussion are almost implemented by Java.Does C ++ have stricter time-constraint than Java on leetcode?
    The C++ version:

    int bfs(string start, string end, set<string> &dict)
        {
             
             queue <string> que;
             int sum = 1;
             que.push(start);
             que.push("\0");
             set<string> visited;
             visited.insert(start);
             int word_len = start.length();
             while (!que.empty()){
                   string tmp = que.front();
                   que.pop();
                   
                   if (tmp == "\0"){
                      sum ++;
                      if (que.empty()){
                         return 0;                 
                      }
                      else {
                           if (tmp == end)return sum;
                           tmp= que.front();
                           que.push("\0");     
                      }
                   }
                   for (int i = 0; i < word_len; i ++){
                       char sav = tmp[i];
                       for (char j = 'a'; j <= 'z'; j ++){
                           
                           tmp[i] = j;
                           if (visited.find(tmp) == visited.end() && dict.find(tmp) != dict.end()){//
                              if (tmp==end)  return sum+1;                        
                              visited.insert(tmp);
                              que.push(tmp);                        
                           }    
                       }    
                       tmp[i] = sav;
                   }
             }
             return 0;
        }
        int ladderLength(string start, string end, set<string> &dict) 
        {
            //initalize the distance array to record the distance between each word in the alphabetic table
            if (start == end)return 1;
            dict.insert(end);
            return bfs(start,end,dict);
        }
    

    The Java version

    public class Solution {
    
    	/**
    	 * @param args
    	 */
    	static int bfs(String start, String end, Set<String> dict)
        {
             
             Queue <String> que = new LinkedList <String>();
             while (!que.isEmpty())que.poll();
             int sum = 1;
             que.add(start);
             que.add("\0");
             Set<String> visited = new HashSet<String>();
             visited.clear();
             int word_len = start.length();
             //System.out.print(word_len);
             //visited[head.str] = true;
             //string str_tmp;
             while (!que.isEmpty()){
                   String tmp = que.poll();
                   
                   if (tmp == "\0"){
                	   
                	  sum ++;
                      if (que.isEmpty()){
                         return 0;                 
                      }
                      else {
                           if (tmp.equals(end))return sum+1;
                           tmp=que.element();
                           que.add("\0");     
                      }
                   }
                   //int jud = count_diff(tmp.str,end);
                   //cout<<"cmp:"<<tmp.str<<' '<< end<<endl;
                   //if (tmp.str==end)  return tmp.sum+1;    
                   for (int i = 0; i < word_len; i ++){
                       char sav = tmp.charAt(i);
                       //System.out.println("i:"+i+' '+sav);
                       for (char j = 'a'; j <= 'z'; j ++){
                    	   tmp=tmp.substring(0, i)+j+tmp.substring(i+1);
                    	   
                           if (!visited.contains(tmp) && dict.contains(tmp)){//
                        	 //System.out.println(tmp);
                              if (tmp.equals(end))return sum+1;                        
                              visited.add(tmp);
                              que.add(tmp);
                           }    
                       }    
                       tmp=tmp.substring(0, i)+sav+tmp.substring(i+1);
                   }
             }
             return 0;
        }
        static int ladderLength(String start, String end, Set<String> dict) 
        {
            //initalize the distance array to record the distance between each word in the alphabetic table
            if (start == end)return 1;
            dict.add(end);
            return bfs(start,end,dict);
        }
    }

Log in to reply
 

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