BFS in Java 37ms with new test case


  • 1

    I modify the answer from Two-end BFS in Java 31ms, because with new test case, that solution will be ETL. Searching in Set is O(1), while searching in List is O(n).

    public class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    		Set<String> wordListSet = new HashSet<String>(wordList);
    		if(!wordListSet.contains(endWord)){
    			return 0;
    		}
            HashSet<String> begin = new HashSet<String>();
            HashSet<String> end = new HashSet<String>();
            HashSet<String> visited = new HashSet<String>();
            int len = 1;
            begin.add(beginWord);
            end.add(endWord);
            while(begin.size() != 0 && end.size() != 0){
                HashSet<String> tmp = new HashSet<String>();
               if(begin.size() > end.size()){
               	HashSet<String> swap = begin;
               	begin = end;
               	end = swap;
               }
                for(String bString:begin){
                    char[] bChar = bString.toCharArray();
                    for(int i = 0; i < bChar.length; i++){
                        for(char j = 'a'; j < 'z'+1; j++){
                            char buff = bChar[i];
                            bChar[i] = j;
                            String bUpdate = String.valueOf(bChar);
                            if(end.contains(bUpdate)){
                            	System.out.println(bUpdate);
                            	return len+1;
                            }
                            if(!visited.contains(bUpdate) && wordListSet.contains(bUpdate)){
                            	visited.add(bUpdate);
                            	tmp.add(bUpdate);
                            }
                            bChar[i] = buff;
                        }
                    }
                }
                len++;
                begin = tmp;
            }
            return 0;
        }
    }
    

Log in to reply
 

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