127 Word Ladder

Leetcode

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

使用广度优先搜索

TODO 使用双向广度优先搜索应该更快一些

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        ArrayList<String> list=new ArrayList<>(wordList);
        int end=list.indexOf(endWord);
        if(end<0) return 0;
        int wordLen=beginWord.length();
        list.add(beginWord);
        int len=list.size();
        boolean[][] graph=new boolean[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if( connected(list.get(i),list.get(j))){
                    graph[i][j]=true;
                    graph[j][i]=true;
                }
            }
        }
        boolean[] visited=new boolean[len];
        visited[len-1]=true;
        int step=1;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(len-1);

        while(!queue.isEmpty()) {
            step++;
//            HashSet<String> set=new HashSet<>();
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                int index = queue.poll();
                if (graph[index][end])
                    return step;
                for (int j = 0; j < len; j++) {
                    if ( !visited[j] && graph[j][index]) {
                        queue.add(j);
                        visited[j]=true;
//                        set.add(list.get(j));
                    }
                }
            }
//            System.out.println("step:"+step+" "+set);
        }
        return 0;
    }
    
    private boolean connected(String s1, String s2){
        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 true;
    }