BFS Java code, without modifying wordList from List to Set


  • 0
    M

    Have no idea why it changes wordList from Set to List, feel free to leave a comment if you have any improvement.

    class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (wordList == null || wordList.size() == 0) {
                return 0;
            }
            if (beginWord.equals(endWord)) {
                return 1;
            }
            if (!wordList.contains(endWord)) {
                return 0;
            }
            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);
            wordList.remove(beginWord);
            int count = 2;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String current = queue.poll();
                    for (int j = 0; j < wordList.size(); j++) {
                        if (oneDifference(current, wordList.get(j))) {
                            if (wordList.get(j).equals(endWord)) {
                                return count;
                            }
                            queue.offer(wordList.get(j));
                            wordList.remove(wordList.get(j));
                            j--;
                        }
                    }
                }
                count++;
            }
            return 0;
        }
        
        public boolean oneDifference(String s1, String s2) {
            int count = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    count++;
                }
            }
            return count == 1;
        }   
    }
    

Log in to reply
 

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