C++LeetCode 실현(126.단어 계단 의 2)

[LeetCode]126.Word Ladder II 단어 계단 2
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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 an empty list 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:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
개인 적 으로 이 문 제 는 상당히 어 려 운 문제 라 고 생각 합 니 다.그것 은 이전 문제 보다.  Word Ladder  복잡 해 야 한다.전체 에서 네 번 째 로 낮은 통 과 률 은 12.9%로 이 문제 의 난이 도 를 설명 했다.블 로 거들 도 인터넷 에서 다른 사람의 해법 을 연구 한 지 오래 되 어서 야 알 아 본 다음 에 조롱박 에 따라 바 가 지 를 그 려 서 썼 다.다음 과 같은 해법 의 핵심 사상 은 BFS 이다.대충 생각 은 다음 과 같다.목적 은 모든 경 로 를 찾 는 것 이다.여기 서 경로 집합 paths 를 구축 하여 모든 경 로 를 보존 하 는 것 이다.그 다음 에 시작 경로 p 입 니 다.p 에서 시작 단 어 를 먼저 넣 습 니 다.그 다음 에 두 개의 정형 변수 level 과 minLevel 을 정의 합 니 다.그 중에서 level 은 순환 중의 현재 경 로 를 기록 하 는 길이 이 고 minLevel 은 가장 짧 은 경 로 를 기록 하 는 길이 입 니 다.이런 장점 은 특정한 경로 의 길이 가 기 존의 가장 짧 은 경로 의 길 이 를 초과 하면 버 리 면 운행 속 도 를 향상 시 키 고 가지치기 에 해당 합 니 다.또한 HashSet 변수 words 를 정의 하여 순환 한 경로 의 단 어 를 기록 합 니 다.그 다음 에 BFS 의 핵심 입 니 다.순환 경로 집합 paths 의 내용 은 팀 의 첫 번 째 경 로 를 추출 합 니 다.만약 에 이 경로 의 길이 가 level 보다 크 면 사전 의 일부 단어 가 이미 경로 에 저장 되 었 음 을 설명 합 니 다.만약 에 경로 에서 중복 되 었 다 면 가장 짧 은 경로 가 아 닐 것 입 니 다.그래서 사전에 서 이 단어 들 을 삭제 한 다음 에 words 를 비우 고 순환 적 으로 가지치기 처리 해 야 합 니 다.그리고 현재 경로 의 마지막 단 어 를 꺼 내 서 모든 알파벳 을 바 꾸 고 사전 에서 바 꾼 새 단어 가 있 는 지 찾 습 니 다.이 과정 은 이전 단계 입 니 다.  Word Ladder  안에 도 있어 요.바 뀐 새 단어 가 사전 에 존재 하면 words 에 추가 하고 기 존 경 로 를 바탕 으로 이 새 단 어 를 추가 하여 새로운 경 로 를 만 듭 니 다.이 새 단어 가 끝 단어 라면 이 새 경 로 는 완전한 경로 입 니 다.결과 에 추가 하고 minLevel 을 업데이트 합 니 다.끝 단어 가 아니라면 새로운 경 로 를 추가 하여 집중 적 으로 순환 합 니 다.이렇게 많이 썼 는데 어 지 러 웠 는 지 모 르 겠 지만 코드 를 보 세 요.이것 이 가장 효과 적 입 니 다.

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        vector<string> p{beginWord};
        queue<vector<string>> paths;
        paths.push(p);
        int level = 1, minLevel = INT_MAX;
        unordered_set<string> words;
        while (!paths.empty()) {
            auto t = paths.front(); paths.pop();
            if (t.size() > level) {
                for (string w : words) dict.erase(w);
                words.clear();
                level = t.size();
                if (level > minLevel) break;
            }
            string last = t.back();
            for (int i = 0; i < last.size(); ++i) {
                string newLast = last;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newLast[i] = ch;
                    if (!dict.count(newLast)) continue;
                    words.insert(newLast);
                    vector<string> nextPath = t;
                    nextPath.push_back(newLast);
                    if (newLast == endWord) {
                        res.push_back(nextPath);
                        minLevel = level;
                    } else paths.push(nextPath);
                }
            }
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/126
유사 한 제목:
Word Ladder
참고 자료:
https://leetcode.com/problems/word-ladder-ii/
http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html
https://leetcode.com/problems/word-ladder-ii/discuss/40487/Java-Solution-with-Iteration
C++구현 LeetCode(126.단어 계단 의 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 단어 계단 의 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!