[LeetCode] 126. Word Ladder II

문제 URL : https://leetcode.com/problems/word-ladder-ii/

Word Ladder II - LeetCode

 

문제 접근법 : 

프로그래머스의 단어 변환 문제와 비슷한데 이게 더 심화문제입니다.

추측으로 프로그래머스에서 이문제를 가져다가 쓴듯한느낌? 아니면 반대일지도?

아무튼

 

문제조건대로 단어 하나만 다를때 인접한 한쌍의 문자라고 하니

단어 하나만 다르다면 변환이 가능합니다. 그변환을 이용해서 beginword 에서 

wordlist를 가지고 있는것을 이용해 변환하여 endword로 만들어  최소의 변환을 이용해 만듭니다.

그치만 경우의수가 여러가지니 그 경우의수를 전부 출력하는 문제입니다.

 

결론만 얘기하자면 우선 beginword -> endword로 만드는 최소변환을 먼저구합니다.

가장 빠른방법은 bfs이고 그경우를 다탐색할 필요는없고 탐색했던것의 하나하나의 단어로 그깊이를 저장합니다.

 

그리고 그깊이를이용해서 endword에서 출발해 beginword를 역추적하여 답을 구한뒤 역추적한거니

해당답을 거꾸로 만들어 답을 담아냅니다.

 

소스코드 :

 

class Solution {
public:
vector<vector<string>> res;
string start, fin;
unordered_map<string, int> check;
vector<string> v;
int h;
int bfs(unordered_set<string> &m)
{
    queue<string> q;
    q.push(start);
    check[start] = 0;
    int ans = 0;
    while (!q.empty())
    {
        int qsize = q.size();
        while (qsize--)
        {
            string cur = q.front();
            q.pop();
            if (cur == fin)
                return ans;
            string next = cur;
            for (int i = 0; i < cur.size(); i++)
            {
                for (char c = 'a'; c <= 'z'; c++)
                {
                    next[i] = c;
                    if (m.count(next) && check.count(next) == 0)
                    {
                        check[next] = ans + 1;
                        q.push(next);
                    }
                }
                next[i] = cur[i];
            }
        }
        ans++;
    }
    return -1;
}

void dfs(string cur, int len, unordered_set<string> &m)
{
    if (len<=0)
    {
        if(!v.empty()&&v.back()==start)
            res.push_back(vector<string>(v.rbegin(),v.rend()));
        return;
    }
    string next = cur;
    for (int i = 0; i < cur.size(); i++)
    {
        for (char c = 'a'; c <= 'z'; c++)
        {
            next[i] = c;
            if(m.count(next)){
                if(check[next]==len-1){
                    v.push_back(next);
                    dfs(next,len-1,m);
                    v.pop_back();
                }
            }
        }
        next[i] = cur[i];
    }
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
{
    unordered_set<string> m(wordList.begin(), wordList.end());
    start = beginWord;
    fin = endWord;
    int len = bfs(m);
    if (len == -1)
        return {};
    v.push_back(fin);
    m.insert(start);
    dfs(fin, len, m);
    return res;
}
};

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.