#
# @lc app=leetcode.cn id=127 lang=python3
#
# [127] 单词接龙
#
# https://leetcode-cn.com/problems/word-ladder/description/
#
# algorithms
# Medium (44.00%)
# Total Accepted:    86.4K
# Total Submissions: 190.3K
# Testcase Example:  '"hit"\n"cog"\n["hot","dot","dog","lot","log","cog"]'
#
# 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord
# 的最短转换序列的长度。转换需遵循如下规则：
# 
# 
# 每次转换只能改变一个字母。
# 转换过程中的中间单词必须是字典中的单词。
# 
# 
# 说明:
# 
# 
# 如果不存在这样的转换序列，返回 0。
# 所有单词具有相同的长度。
# 所有单词只由小写字母组成。
# 字典中不存在重复的单词。
# 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
# 
# 
# 示例 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" 不在字典中，所以无法进行转换。
# 
#
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def diff(s1,s2):
            symbol = False
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    if symbol:
                        return False
                    else:
                        symbol = True
            return True

        wordList = [beginWord] + wordList
        d = {}
        for i in range(len(wordList)):
            for j in range(i,len(wordList)):
                s1 = wordList[i]
                s2 = wordList[j]
                if diff(s1,s2):
                    d[s1] = d.get(s1,[]) + [s2]
                    d[s2] = d.get(s2,[]) + [s1]

        b_words = [beginWord]
        visited_words = []
        count = 0
        while b_words:
            e_words = []
            for word in b_words:
                if word in visited_words:
                    continue
                visited_words.append(word)
                e_words += d[word]
            e_words = list(set(e_words))
            count += 1
            if endWord in e_words:
                return count+1
            b_words = e_words
        return 0
