127. 单词接龙

题意：

解题思路：

思路：双向BFS
1. begin: [hit] -> [hot] + 1 -> [dot, lot] + 1, end: [cog];
2. begin: [cog] -> [cog, dog, log] + 1, end: [dot, lot];
3. begin: [dot, log] -> dog + 1, end: [cog, dog, log];
4. 由于dog在end[cog, dog, log]中有交集，故找到相交点;

PHP代码实现：

class Solution {
    /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return Integer
     */
    function swap(&$s1, &$s2) {
        $temp = $s1;
        $s1 = $s2;
        $s2 = $temp;
    } 
    function ladderLength($beginWord, $endWord, $wordList) {
        if (!in_array($endWord, $wordList)) return 0;
        $wordList = array_flip($wordList);
        $s1[] = $beginWord;
        $s2[] = $endWord;
        $n = strlen($beginWord);
        $step = 0;
        while (!empty($s1)) {
            $step++;
            if (count($s1) > count($s2)) {
                $this->swap($s1, $s2);
            }
            $s = [];
            foreach ($s1 as $wordstr) {
                for ($i = 0; $i < $n; $i++) {
                    $word = $wordstr;
                    for ($ch = ord('a'); $ch <= ord('z'); $ch++) {
                        $word[$i] = chr($ch);
                        if (in_array($word, $s2)) {
                            return $step + 1;
                        }
                        if (!array_key_exists($word, $wordList)) {
                            continue;
                        }
                        unset($wordList[$word]);
                        $s[] = $word;
                    }
                }
            }
            $s1 = $s;
        }
        return 0;
    }
}

GO代码实现：

func ladderLength(beginWord string, endWord string, wordList []string) int {
    dict := make(map[string]bool) // 把word存入字典
    for _, word := range wordList {
        dict[word] = true // 可以利用字典快速添加、删除和查找单词
    }
    if _, ok := dict[endWord]; !ok {
        return 0
    }
    s1 := make(map[string]bool)
    s2 := make(map[string]bool)
    s1[beginWord] = true // 头
    s2[endWord] = true   // 尾
    l := len(beginWord)
    steps := 0
    for len(s1) > 0 && len(s2) > 0 { // 当两个集合都不为空，执行
        steps++
        // Always expend the smaller queue first
        if len(s1) > len(s2) {
            s1, s2 = s2, s1
        }
        q := make(map[string]bool) // 临时set
        for k := range s1 {
            chs := []rune(k)
            for i := 0; i < l; i++ {
                ch := chs[i]
                for c := 'a'; c <= 'z'; c++ { // 对每一位从a-z尝试
                    chs[i] = c // 替换字母组成新的单词
                    t := string(chs)
                    if _, ok := s2[t]; ok { // 看新单词是否在s2集合中
                        return steps + 1
                    }
                    if _, ok := dict[t]; !ok { // 看新单词是否在dict中
                        continue // 不在字典就跳出循环
                    }
                    delete(dict, t) // 若在字典中则删除该新的单词，表示已访问过
                    q[t] = true     // 把该单词加入到临时队列中
                }
                chs[i] = ch // 新单词第i位复位，还原成原单词，继续往下操作
            }
        }
        s1 = q // s1修改为新扩展的q
    }
    return 0
}