[LeetCode] 127. Word Ladder 문제 풀이 보고서 (Python)

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
제목 주소:https://leetcode.com/problems/word-ladder/description/
제목 설명:
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.

Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return 0 if there is no such transformation sequence.

All words have the same length.

All words contain only lowercase alphabetic characters.

You may assume no duplicates in the word list.

You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
제목 의 대의
이 문제 의 이름 은 단어 사다리 입 니 다. 간단하게 이해 하면 begin 부터 매번 전 환 된 단어의 한 글자 만 바 꿀 수 있 고 최종 적 으로 end 를 얻 을 수 있 는 지 없 는 지 를 볼 수 있 습 니 다.매번 변화 하 는 것 은 임 의적 인 것 이 아니 라 wordList 중의 하나 가 되 어야 한 다 는 요구 가 있다.
문제 풀이 방법
이 문 제 를 얻 으 면 아무런 생각 이 없어 서 다른 사람 이 풀 어 주 는 것 을 보고 나 서 야 이 문 제 는 미로 문제 의 변형 이라는 것 을 갑자기 알 게 되 었 다!즉, 우 리 는 매번 변화 할 때마다 26 개의 방향 이 있다. 만약 변화 후의 위치 가 wordList 에 있다 면 우 리 는 이 방법 이 규정 에 부합 한다 고 생각한다. 마지막 으로 endWord 에 갈 수 있 느 냐 고 묻는다.
분명히 이 문 제 는 BFS 의 문제 이다. 미로 문제 의 4 개 방향 을 26 개 방향 으로 바 꾸 었 을 뿐 이 고 BFS 가 시간 을 초과 할 것 이다. 그래서 나 는 이미 지나 간 문자열 을 저장 하기 위해 visited 를 사용 했다.코드 의 전체적인 사고방식 은 매우 간단 하 다. 바로 대기 열 을 이용 하여 모든 유효한 문자열 을 저장 한 다음 에 대기 열 에 있 는 모든 문자열 을 다시 옮 겨 다 니 며 매번 옮 겨 다 니 는 길 이 를 저장 하면 된다.
시간 복잡 도 는 O (NL) 이 고 공간 복잡 도 는 O (N) 입 니 다. 그 중에서 N 은 wordList 의 단어 개수 이 고 L 은 실제 문자열 의 길이 입 니 다.

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordset = set(wordList)
        if endWord not in wordset:
            return 0
        visited = set([beginWord])
        chrs = [chr(ord('a') + i) for i in range(26)]
        bfs = collections.deque([beginWord])
        res = 1
        while bfs:
            len_bfs = len(bfs)
            for _ in range(len_bfs):
                origin = bfs.popleft()
                for i in range(len(origin)):
                    originlist = list(origin)
                    for c in chrs:
                        originlist[i] = c
                        transword = "".join(originlist)
                        if transword not in visited:
                            if transword == endWord:
                                return res + 1
                            elif transword in wordset:
                                bfs.append(transword)
                                visited.add(transword)
            res += 1
        return 0

분명히 위의 이 방법 은 조금 짧 아 질 수 있 습 니 다. 예전 의 이 진 트 리 의 BFS 를 생각 할 때 모든 노드 가 대기 열 에 들 어 갈 때 이 노드 의 깊이 를 동시에 저장 합 니 다. 그러면 bfs 의 현재 길이 에 대한 순환 이 줄 어 들 고 코드 를 짧게 할 수 있 습 니 다.또한, 이미 옮 겨 다 니 는 위 치 를 wordList 에서 직접 삭제 하 는 기술 을 배 웠 습 니 다. 이것 은 제 위의 visited 배열 에 해당 합 니 다.아래 의 이 코드 는 매우 고전적 이어서 기억 할 수 있다.

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordset = set(wordList)
        bfs = collections.deque()
        bfs.append((beginWord, 1))
        while bfs:
            word, length = bfs.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    newWord = word[:i] + c + word[i + 1:]
                    if newWord in wordset and newWord != word:
                        wordset.remove(newWord)
                        bfs.append((newWord, length + 1))
        return 0

참고 자료:
http://www.cnblogs.com/grandyang/p/4539768.html
날짜.
2018 년 9 월 29 일 - 국경절 9 일 연 휴 첫날!