My JAVA BFS Solution


  • 0
    R
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> list = new ArrayList<List<String>>();//存放最后结果
            List<String> subList = new ArrayList<String>();//存放部分结果
            Queue<List<String>> queue = new LinkedList<List<String>>();//路径的queue用作进行BFS
            Set<String> set = new HashSet<String>();//用作排重
            boolean flag = false;//用作标志是否已经走到了尽头
            int len = Integer.MAX_VALUE;//用作最短路径长度
            wordList.add(endWord);//将tail放到wordList中去
            wordList.remove(beginWord);//将head从wordList里面删除
            subList.add(beginWord);//将head放入到subList里面去
            queue.offer(subList);//将部分路径放到queue里面进行BFS
            while(!queue.isEmpty() && !flag){
                int size = queue.size();
                for(int i = 0; i < size; i++){
                    List<String> path = queue.poll();
                    if(path.size() >= len){//如果path的长度超过最长长度,break
                        flag = true;
                        break;
                    }
                    String lastWord = path.get(path.size() - 1);//get最后一个path的tail
                    char[] arr = lastWord.toCharArray();
                    for(int j = 0; j < arr.length; j++){
                        char original = arr[j];//保存原值
                        for(char c = 'a'; c <= 'z'; c++){
                            arr[j] = c;
                            String newWord = new String(arr);
                            if(wordList.contains(newWord)){
                                List<String> newPath = new ArrayList<String>(path);
                                newPath.add(newWord);
                                set.add(newWord);
                                if(newWord.equals(endWord)){
                                    len = newPath.size();
                                    list.add(newPath);
                                }
                                else{
                                    queue.offer(newPath);
                                }
                            }
                        }
                        arr[j] = original;//恢复原值
                    }
                }
                wordList.removeAll(set);
                set.clear();
            }
            return list;
        }
    }
    

Log in to reply
 

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