BFS+Set with Java solution


  • 0
    R

    public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    // BFS
    // put wotdlist into set
    if (wordList == null || wordList.size() == 0) return 0;
    HashSet<String> set = new HashSet<>();
    for(String str : wordList) { set.add(str); }
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int res = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            for (int i = 0; i < size; i++) {
                String temp = queue.poll();
                // get the matched subnode, if get a string equals endword then return; else put this element into queue
                char[] tempch = temp.toCharArray();
                for (int j = 0; j < temp.length(); j++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if ( ch != temp.charAt(j) ) {
                            char midch = tempch[j];
                            tempch[j] = ch;
                            String result = String.valueOf(tempch);
                            // judge whether this result is end or inside this set
                            if (set.contains(result)) {
                                if(result.equals(endWord)) {
                                    return res;
                                }
                                queue.offer(result);
                                set.remove(result);
                            }
                            tempch[j] = midch;
                            result = String.valueOf(tempch);
                        }
                    }
                }
            }
        }
        return 0;
    }
    

    }


Log in to reply
 

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