C++LeetCode(127.단어 계단)실현

[LeetCode]127.Word 사다리
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.
이 어구 계단 의 문 제 는 우리 에 게 단어 사전 을 주 었 다.그 안에 비슷 한 단어 들 이 일련의 시작 단어 와 끝 단 어 를 주 었 다.매번 에 한 단어 만 바 꿀 수 있 고 중간 과정 에 있 는 단 어 는 단어 사전 의 단어 여야 한다.우 리 는 가장 짧 은 변화 서열 의 길 이 를 구 할 수 있다.이 문 제 는 어 려 운 문제 입 니 다.저 는 당연히 다른 사람의 해법 을 보고 쓴 것 입 니 다.아무것도 아 닙 니 다.완전히 파악 할 줄 모 르 는 것 이 성장 입 니 다~
문 제 를 받 으 면 어 리 석 은 우 리 는 어떻게 해야만 과학적 인 탐색 문제 풀이 의 경 로 를 찾 을 수 있 습 니까?그것 은 코드 실현 에 관여 하지 않 는 것 입 니 다.만약 에 우리 가 육신 으로 문 제 를 풀 게 한다 면 어떻게 해 야 합 니까?'hit'를'cog'으로 바 꿔 보 자.그러면 우 리 는 이 두 단어 에 똑 같은 자모 가 하나 도 없다 는 것 을 알 게 되 었 다.그래서 우 리 는 시도 해 보 자.블 로 거들 은 먼저 첫 번 째'h'를'c'로 바 꾸 고'cit'가 사전 에 있 는 지 없 는 지,없 는 지 를 보 자.그러면 두 번 째'i'를'o'로 바 꾸 고'hot'가 있 는 지,없 는 지,있 는 지,완벽 한 지 를 보 자!그리고'cot'나'hog'을 시도 해 보 세 요.모두 없 는 것 을 발견 하면 귀 찮 습 니 다.우 리 는 목표 단 어 를 빨리 달성 하지 못 하고 중간 상태 가 필요 합 니 다.그러나 우 리 는 중간 상태 가 무엇 인지 어떻게 압 니까?간단 하고 거 친 방법 은 brute force 입 니 다.모든 상황 을 옮 겨 다 니 며 우 리 는 시작 단어의 모든 자 모 를 26 개의 자모 로 바 꿉 니 다.예 를 들 어 시작 단어 인'hit'는'ait','bit','cit',...'yit','zit'로 바 꾸 고 모든 단 어 를 사전에 서 찾 아 보 세 요.있 으 면 잠재 적 인 경로 일 수 있 으 므 로 저장 해 야 합 니 다.그러면 지금 문제 가 있 습 니 다.예 를 들 어 우리 가'hot'으로 바 뀌 었 을 때 사전 에 존재 하 는 것 을 발 견 했 습 니 다.그러면 다음 단 계 는 다음'hpt','hqt','hrt'를 계속 시험 해 보 는 것 입 니까?아니면'hot'의 이니셜 부터'aot','bot','cot'를 바 꾸 는 것 입 니까?이것 은 실제 적 으로 BFS 와 DFS 의 차이 입 니 다.넓이 가 우선 입 니까?깊이 가 우선 입 니까?여기까지 만 말 하면 이것 이 무엇 과 비슷 하 다 고 생각 하 십 니까?참,미로 가 널 려 있 는 것 과 비슷 하 네요.생각해 보 세 요.미로 의 모든 점 은 상하 좌우 네 방향 으로 갈 수 있 고 여 기 는 26 개의 자모 가 있 습 니 다.바로 26 개의 방향 으로 갈 수 있 습 니 다.본질 적 으로 다 를 것 이 없습니다!미로 에 익숙 한 어린이 신발 들 은 BFS 로 가장 짧 은 경로 의 길 이 를 구 해 야 한 다 는 것 을 알 아야 한다.이것 도 이해 하기 어렵 지 않다.DFS 는 한 길 로 어두 운 길 로 가 는 것 과 같다.네가 가 는 그 길이 가 반드시 가장 짧 은 길 은 아니다.한편,BFS 는 작은 원 하나 가 천천히 한 층 씩 확대 되 는 것 과 같 고 호수 에 돌 을 던 지 는 것 과 같 으 며 한 바퀴 씩 확대 되 는 물결 무늬 의 느낌 이다.물결 무늬 가 호수 에 있 는 나뭇잎 에 닿 았 을 때 이때 물 바퀴 의 반지름 은 원심 에서 나뭇잎 까지 의 가장 짧 은 거리 이다.머 릿 속 에 이 생생 한 장면 이 떠 오 르 지 않 았 나 요?
BFS 를 사용 해 야 한 다 는 것 을 명 확 히 했 습 니 다.우 리 는 사전 의 검색 효율 을 언급 하기 위해 HashSet 을 사용 하여 모든 단 어 를 저장 할 수 있 습 니 다.그 다음 에 우 리 는 특정한 경로 의 끝 단어 와 이 경로 의 길이 사이 의 맵 을 만 들 고 시작 단 어 를 1 로 표시 해 야 합 니 다.BFS 인 이상 시작 단 어 를 대열 에 배열 하고 대열 의 순환 을 시작 하 며 팀 의 첫 단 어 를 꺼 낸 다음 각 위치 에 있 는 문 자 를 26 글자 로 교체 해 야 합 니 다.이때 마지막 단어 와 같 으 면 추출 단어 가 해시 표 에 있 는 값 에 하 나 를 추가 할 수 있 습 니 다.사전 에 대체 어가 존재 하지만 해시 표 에 존재 하지 않 는 다 면 대체 어 를 대기 열 에 배열 하고 해시 표 의 값 을 표시 하기 전에 단 어 를 하나 더 추가 합 니 다.순환 이 완료 되면 0 으로 돌아 갑 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;
        unordered_map<string, int> pathCnt{{{beginWord, 1}}};
        queue<string> q{{beginWord}};
        while (!q.empty()) {
            string word = q.front(); q.pop();
            for (int i = 0; i < word.size(); ++i) {
                string newWord = word;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newWord[i] = ch;
                    if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
                    if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
                        q.push(newWord);
                        pathCnt[newWord] = pathCnt[word] + 1;
                    }   
                }
            }
        }
        return 0;
    }
};

사실 우 리 는 위의 해법 중의 HashMap 을 필요 로 하지 않 습 니 다.BFS 의 스 트 리밍 체 제 는 한 층 한 층 확대 되 기 때문에 우 리 는 층수 만 기억 하면 됩 니 다.그리고 while 순환 에서 작은 trick 를 사용 하고 for 순환 을 추가 하면 현재 대열 의 한 수 를 옮 겨 다 닌 후에 층수 가 1 이 증가 한 다 는 것 을 의미 합 니 다.그러면 우 리 는 HashMap 을 절약 할 수 있 습 니 다.그리고 하나의 변수 res 로 층 수 를 기록 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;
        queue<string> q{{beginWord}};
        int res = 0;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                string word = q.front(); q.pop();
                if (word == endWord) return res + 1;
                for (int i = 0; i < word.size(); ++i) {
                    string newWord = word;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        newWord[i] = ch;
                        if (wordSet.count(newWord) && newWord != word) {
                            q.push(newWord);
                            wordSet.erase(newWord);
                        }   
                    }
                }
            }
            ++res;
        }
        return 0;
    }
};

유사 한 제목:
Word Ladder II
Minimum Genetic Mutation
참고 자료:
https://leetcode.com/problems/word-ladder/description/
https://leetcode.com/problems/word-ladder/discuss/40728/Simple-Java-BFS-solution-with-explanation
C++구현 LeetCode(127.단어 계단)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 단어 계단 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!