easy understand java solution with BFS


  • 0
    C

    I met this wrong answer :

    Input:
        "a"
        "c"
        ["a","b","c"]
    Output:
        1
    Expected:
        2
    

    but i think my answer is right, "a" could change one char to "c" directly. can someone make me understand this? below is my code.

    public class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> wordSet = new HashSet<>(wordList);
            
            if( wordSet.isEmpty() || !wordSet.contains(endWord)) return 0;
            
            Queue<String> queue = new LinkedList<>();
            queue.add(beginWord);
            wordSet.add(endWord);
            String word;
            int len = 0;
            Set<String> visited = new HashSet<>();
            
            while ( (word = queue.poll()) != null ) {
                
                for (String dict : wordSet) {
                    
                    if (visited.contains(dict)) continue;
                    
                    if (isDifferOneChar(word, dict)) {
                        
                        if (endWord.equals(dict)) {
                            return len + 1;
                        }
                        
                        queue.add(dict);
                        visited.add(dict);
                        // wordSet.remove(dict);
                    }
                }
                len ++;
            }
            return 0;
        }
        
        public boolean isDifferOneChar(String word1, String word2) {
            char[] ch1 = word1.toCharArray();
            char[] ch2 = word2.toCharArray();
            int cnt = 0;
            
            for (int i=0; i < ch1.length; i++) {
                if(ch1[i] != ch2[i]) {
                    cnt ++;
                    if (cnt > 1) {
                        return false;
                    }
                }
            }
            
            if (cnt == 1) {
                return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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