leetcode:127. Word Solitaire

127. 单词接龙

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/word-ladder/

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母.
• 对于 1 <= i <= k 时,每个 si 都在 wordList 中.注意, beginWord 不需要在 wordList 中.
• $s_k==endWord$

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 .如果不存在这样的转换序列,返回 0 .

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5.

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中,所以无法进行转换.

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

解法

• 广度优先遍历BFS：经过分析可知,题目要求将一个基因序列 A变化至另一个基因序列 B,需要满足一下条件：
  • 序列 A 与 序列 B 之间只有一个字符不同;
  • 变化字符只能从26Choose from lowercase letters;
  • 变换后的序列 B 一定要在字符串数组 wordlist 中, 可以将wordlist转成set加快速度;
    如果start==end,直接返回0;如果end不在wordli身体、中或者wordlist长度为空,返回0;然后开始遍历start,start的每个字符都有可能发生26种变化,变化后需要基于wordlist检测变化后的合法性,如果变化后等于end,返回变化的次数,因此这里需要同步一个变量保存变化的次数.注意,每次确定变化合法后,但又不等于end时候,要从wordlist中将该字符串去掉,不然就容易形成环路,一直循环下去了.

代码实现

BFS

python实现

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if beginWord == endWord:
            return 0
        
        if endWord not in wordList:
            return 0
        wordList = set(wordList)
        queue = [(beginWord, 1)]
        while queue:
            current_str, step = queue.pop(0)
            for i, x in enumerate(current_str):
                for y in 'abcdefghijklmnopqrstuvwxyz':
                    if x != y:
                        next_str = current_str[:i] + y + current_str[i+1:]
                        if next_str in wordList:
                            if next_str == endWord:
                                return step+1
                            wordList.remove(next_str)
                            queue.append((next_str, step+1))
        return 0

c++实现

class Solution {
    
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    
        unordered_set<string> cnt;
        queue<pair<string, int>> q;
        string key = "abcdefghijklmnopqrstuvwxyz";
        for(auto &w: wordList)
            cnt.emplace(w);
        
        if (beginWord == endWord)
            return 0;
        
        if (!cnt.count(endWord))
            return 0;
        
        q.push({
    beginWord, 1});
        while (!q.empty()) {
    
            pair curr = q.front();
            q.pop();
            string curr_string = curr.first;
            int curr_step = curr.second;
            for (int i=0; i< curr_string.size(); i++) {
    
                for(int j=0; j<key.size(); j++) {
    
                    if (key[j] != curr_string[i]) {
    
                        string nxt = curr_string;
                        nxt[i] = key[j];
                        if (cnt.count(nxt)){
    
                            if (nxt == endWord)
                                return curr_step+1;
                            
                            cnt.erase(nxt);
                            q.push({
    nxt, curr_step+1});
                        }
                    }
                }
            }
        }
        return 0;
    }
};

复杂度分析

• 时间复杂度： $O(N\ast M\ast C)$, N是字符串start的长度,C是可变次数,这里C=26,M是wordlist的长度;
• 空间复杂度： $O(N\ast M)$ , N是字符串start的长度,M是wordlist的长度,队列中最多有 M 个元素,每个元素的空间为 O(n),因此空间复杂度为$O(N\times M)$.