Word Ladder I&&II （Snapchat）

2016-11-23 晚上 Bobst

这两道题乍一看是String的题，其实是隐式图的搜索问题，每个单词是一个节点，相邻的单词是边。

既然是求最短的变换距离，那么肯定是用BFS来做比较方便。也就是用BFS求两点之间的最短距离问题。

Word Ladder I

一个比较标准的BFS解法

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(beginWord ==null || endWord==null || beginWord.length()==0 ||
         endWord.length()==0 || beginWord.length()!=endWord.length())  
            return 0;  

        // bfs, find the adjacent word
        wordList.add(beginWord);
        wordList.add(endWord);

        Queue<String> q = new LinkedList<>();
        HashSet<String> set = new HashSet<>();
        q.add(beginWord);
        set.add(beginWord);

        int step = 1;

        while(!q.isEmpty()) {
            int size = q.size();
            step++;
            for (int i = 0; i < size; i++) {
                String curWord = q.poll();
                ArrayList<String> adjacentWord = getNextWord(curWord, wordList);
                for(String nextWord:adjacentWord) {
                    if(set.contains(nextWord)) {
                        continue;
                    }
                    if(nextWord.equals(endWord)) {
                        return step;
                    } 
                    if(!set.contains(nextWord)) {
                        q.offer(nextWord);
                        set.add(nextWord);
                    }
                }
            }

        }
        return 0;
    }

    public ArrayList<String> getNextWord(String word, Set<String> wordList) {
        ArrayList<String> result = new ArrayList<>();
        for(int i = 0; i < word.length(); i++) {
            for(char c = 'a'; c <= 'z'; c++) {
                String next = word.substring(0, i) + c + word.substring(i + 1);
                if(wordList.contains(next)) {
                    result.add(next);
                }
            }
        }

        return result;
    }
}

但是这个做法有一个问题，就是在大数据集的时候，由于每个单词变化的可能性过多，导致实际复杂度很高，解决方法就是 bi-directional，从两头开始往中间搜索，每次都去选择小的数据集的那头开始。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(wordList == null || wordList.isEmpty() || beginWord == null || endWord == null) {
            return 0;
        }
        if(beginWord.equals(endWord)) return 2;

        HashSet<String> beginSet = new HashSet<>();
        HashSet<String> endSet = new HashSet<>();

        // avoid circle
        wordList.remove(beginWord);
        wordList.remove(endWord);

        beginSet.add(beginWord);
        endSet.add(endWord);

        int step = 2;

        while(!beginSet.isEmpty()) {
            HashSet<String> nextLevel = new HashSet<>();
            for(String word : beginSet) {
                char[] chars = word.toCharArray();
                for(int i = 0; i < chars.length; i++) {
                    for(char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String newWord = String.valueOf(chars);

                        if(endSet.contains(newWord)) return step;
                        if(wordList.contains(newWord)) {
                            nextLevel.add(newWord);
                            wordList.remove(newWord);
                        }
                    }
                    // change back
                    chars = word.toCharArray();
                }

            }
            step++;

            // which side has less size
            if(nextLevel.size() < endSet.size()) {
                beginSet = nextLevel;
            } else {
                beginSet = endSet;
                endSet = nextLevel;
            }
        }

        return 0;
    }
}

Word Ladder II

返回所有最短距离的path

维护一个 Directed Graph 关系并且从某一个终点进行 dfs 返回所有 valid path.

这题应对大数据集的解法是 Bi-directional BFS 与 DFS 的结合，因为 bfs 过程中起点终点会调换，为了保证 path 的正确性要 keep track of direction.

有向图找最短距离用 BFS

有向图返回所有路径用 DFS

代码太麻烦了，就先放在这儿，有时间再慢慢写。