Short Java BFS solution


  • 4
    T
    public int ladderLength(String start, String end, Set<String> dict) {
        LinkedList<String> queue = new LinkedList<String>();
        queue.add(start);
        dict.add(end);
        int step = 0;
        while (!queue.isEmpty()) {
            LinkedList<String> level = new LinkedList<String>();
            step++;
            while (!queue.isEmpty()) {
                String q = queue.pollFirst();
                if (q.equals(end))
                    return step;
                for (int i = 0; i < start.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String s = q.substring(0, i) + c + q.substring(i + 1, start.length());
                        if (dict.contains(s)) {
                            level.add(s);
                            dict.remove(s);
                        }
                    }
                }
            }
            queue = level;
        }
        return 0;
    }

  • 0
    L

    Time Limit Exceeded. Test before post.


  • 0
    C

    Time Limit Exceeded.


  • 0
    C

    The code is mostly good.

    change queue.pollFirst() to queue.poll(), TLE should be gone.


  • 0
    P

    It's better not to use string concatenation which would cause TLE. Try using toCharArray instead.


  • -2
    S
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
    
        int path = 0;
        if(beginWord.equals(endWord)) return ++path;
    
        Queue<String> bfs = new LinkedList<>();
        bfs.add("0");
        bfs.add(beginWord);
        wordDict.remove(beginWord);
    
        while(bfs.size() > 1){
            String curr = bfs.remove();
            if(curr.equals("0")){
                path++;
                bfs.add(curr);
            }else{
                String nbr = "";
                //Generate all adjacent words of curr
                for(int i=0; i<curr.length(); i++){
                    for(char c = 'a'; c<= 'z'; c++){
                            nbr = curr.substring(0,i)+c+curr.substring(i+1);
                            if(endWord.equals(nbr)) return ++path;
                            if(wordDict.remove(nbr)){
                                 bfs.add(nbr);
                            }
                    }
                } //for
            } //if/else
        }//end of while
        return 0;
    }

  • 0
    F

    time limit~~~


  • 0
    Z

    pollFirst() and poll() are same, still have TLE.

       public E poll() {
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
    
       public E pollFirst() {
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
    

  • 13
    L
    public int ladderLength(String start, String end, Set<String> dict) {
        LinkedList<String> queue = new LinkedList<String>();
    	queue.add(start);
    	dict.add(end);
    	int step = 0;
    	
    	while (!queue.isEmpty()) {
    		LinkedList<String> level = new LinkedList<String>();
    		step++;
    		while (!queue.isEmpty()) {
    			String q = queue.poll();
    			if(q.equals(end))
    				return step;
    			
    			char[] t = q.toCharArray();
    			for(int i = 0; i < start.length(); i++){
    				for(char c = 'a'; c <= 'z'; c++){
    					char temp = t[i];
    					t[i] = c;
    					String s = String.copyValueOf(t);
                        t[i] = temp;
    					if(dict.contains(s)){
    						level.add(s);
    						dict.remove(s);
    					}
    				}
    			}
    		}
    		queue = level;
    	}
    
    	return 0;
    }
    

    The solution is pretty good. I modify the part of string concatenation and it runs with 476 ms.


  • 0
    S

    pretty good answers ,expand my views


Log in to reply
 

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