Why am I getting timeout? And what kind of timeout is it? It took 2ms to run locally.


  • 0
    G

    My code runs fine on Eclipse, but when I submitted to OJ it says timeout. How could I find out what the timeout is?

    public int ladderLength(String start, String end, Set<String> dict) {
        if (start == null || end == null || start.equals(end))
            return 0;
        
        if (distance(start,end) == 1) return 2;
        
        // construct linked sets based on the distance of words from original
        HashMap<Integer, HashSet<String>> startmap = new HashMap<Integer, HashSet<String>>();
    
        HashSet<String> startset = null;
        HashSet<String> endset = new HashSet<String>();
        
        for (String s : dict) {
            int diststart = distance(start, s);
            int distend = distance(end, s);
            if (diststart > 0) {
                if (startmap.containsKey(diststart)) {
                    startset = startmap.get(diststart);
                } else {
                    startset = new HashSet<String>();
                    startmap.put(diststart, startset);
                }
                startset.add(s);
            }
            // we only need the distance 1 to match those in the startset
            if (distend==1) {
                endset.add(s);
            }
        }
    
        // if one of the word does not have any transformation in dictionary
        if (startmap.size()==0 || endset.size()==0) return 0;
    
        // walk the path
        boolean success = false;
        int dist = 2;
        
        for (int dstart=1; dstart<=startmap.size(); ++dstart) {
            dist++;
            // if dstart goes from 2 to 4 without having a distant 3, break
            if (!startmap.containsKey(dstart)) break;
            
            startset = startmap.get(dstart);
    
            // see if they intersect
            if (hasCommon(startset, endset)) {
                success = true;
                break;
            }
        }
        return success ? dist : 0;
    }
    
    private int distance(String left, String right) {
        int d = 0;
        for (int i=0; i<left.length(); ++i) {
            if (left.charAt(i) != right.charAt(i))
                d++;
        }
        
        return d;
    }
    private boolean hasCommon(HashSet<String> set1, HashSet<String> set2) {
        boolean success = false;
        for (String s : set1) {
            if (set2.contains(s)) {
                success = true;
                break;
            }
        }
        
        return success;
    }

  • 0
    S

    Do you mean time out or time limit exceeded ? Check out the difference between them in OJ FAQ. I submitted this code. The result is Wrong Answer.


Log in to reply
 

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