127. Word Ladder
in leetcode with 0 comment

127. Word Ladder

in leetcode with 0 comment

127. Word Ladder

原题链接 127. Word Ladder

image-20200419210053473

解题思路

由题目可得我们需要判断一个单词通过词典列表给的词是否能转换到另一个单词 如果能最少转换次数是多少,且每次转换只能转换一个字符。

其实我们完全可以把这个过程抽象成一个图,那么这题就变成了图中一个节点到另一个节点的最短路径。

Word_Ladder_1.png

在图中 求最短路径可以通过bfs算法实现。

AC代码

 // bfs
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
         if (!wordList.contains(endWord)) {
            return 0;
        }
        // visited修改为boolean数组
        boolean[] visited = new boolean[wordList.size()];
        int idx = wordList.indexOf(beginWord);
        if (idx != -1) {
            visited[idx] = true;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int count = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
             count++;
            for(int i = 0; i <  size; i++) {
                String word = queue.poll();
                for(int j = 0; j < wordList.size(); j++) {
                    if(visited[j]) {
                        continue;
                    }
                    String s = wordList.get(j);
                    if(!canConvert(word, s)) {
                        continue;
                    }
                    if(endWord.equals(s)) {
                        return ++count;
                    }
                    queue.offer(s);
                    visited[j] = true;
                }
            }
           
            
        }
        return 0;
    }
    
    
    private boolean canConvert(String s1, String s2) {
         // 因为题目说了单词长度相同,可以不考虑长度问题
        // if (s1.length() != s2.length()) return false;
        int count = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++count;
                if (count > 1) {
                    return false;
                }
            }
        }
        return count == 1;
    }