BFS Java Solution after param input changed


  • 0
    M

    Normal BFS Solution after the input has been changed to list format.

    public class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> words = new HashSet<>();
            for (String s : wordList) {
                words.add(s);
            }
    
            Queue<String> visited = new ArrayDeque<>();
            Set<String> visistedSet = new HashSet<>();
    
           visited.add(beginWord);
           visistedSet.add(beginWord);
    
    
            int count = 1;
            while(!visited.isEmpty()) {
                int t = visited.size();
                count++;
                for (int i = 0; i < t; i++) {
                String current = visited.poll();
                    for (int p = 0; p < current.length(); p++) {
                        char[] chars = current.toCharArray();
                        for (char k = 'a'; k <= 'z'; k++) {
                            chars[p] = k;
                            String w = new String(chars);
                            if (words.contains(w) && w.equals(endWord)) {
                                return (count);
                            } else if (visistedSet.contains(w)) {
                                continue;
                            } else if (words.contains(w) && !w.equals(current)) {
                                visited.add(w);
                                visistedSet.add(w);
                            }
                        }
                    }
                }
            }
            return 0;
        }
    
    }
    

Log in to reply
 

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