LC126: Word Ladder II

https://leetcode.com/problems/word-ladder-ii/

  • 연휴동안 100문제 풀기 (1/100)
  • 57분 42초
  • 처절한 메모리, 시간초과와의 싸음
  • 풀었는데 526ms, Best는 24ms..
  • 일단 키 아이디어는 지난번 레벨에 이미 도달한 Node에는 갈 필요없다. 내리막길을 BFS로 내려가는 BFS-DP와 유사한 유형.
  • [추가 아이디어] 양방향 BFS란다.. Refrenece
    • 양쪽 끝을 알고, 그래프가 클 경우에는 Bidirection-BFS가 빠를 수 있다.

BFS-DP, 526ms, 1/25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
struct Node {
    int n;
    Node* prev;
};

Node myQueue[5000 * 10000];
class Solution {
public:
    int fp, bp;
    void push(int n, Node* p) { myQueue[bp++] = {n,p}; }
    Node* pop() { return &myQueue[fp++]; }
    int qsize() { return bp - fp; }
    
    int getEndIndex(vector<string>& wordList, string& endWord) {
        for(int i = 0; i < wordList.size(); i++)
            if (wordList[i] == endWord)
                return i;
        return -1;
    }
    
    int checkDiff(string& a, string& b, int cnt = 0) {
        for(int i = 0; i < a.size(); i++)
            if(a[i] != b[i]) cnt++;
        return cnt;
    }
    
    vector<vector<int>> adj;
    void createGraph(vector<string>& wordList) {
        adj.resize(wordList.size());
        for(int i = 0; i < wordList.size(); i++) {
            for(int j = i+1; j < wordList.size(); j++) {
                if(checkDiff(wordList[i], wordList[j]) == 1) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
    }
    
    bool isVisited(Node* cur, int near) {
        while(cur) {
            if(cur->n == near) return true;
            cur = cur->prev;
        }
        return false;
    }
    
    vector<vector<string>> ans;
    void collectPath(vector<string>& wordList, Node* cur, int endIdx) {
        vector<string> curList = {wordList[endIdx]};
        while (cur) {
            curList.push_back(wordList[cur->n]);
            cur = cur->prev;
        }
        reverse(curList.begin(), curList.end());
        ans.push_back(curList);
    }
    
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        int endIdx = getEndIndex(wordList, endWord);
        if(endIdx == -1) return {};
        createGraph(wordList);
        
        push(wordList.size() - 1, nullptr);
        vector<int> dp(wordList.size(), INT_MAX);
        
        int dist = 0;
        while(qsize() && !ans.size()) {
            dist++;
            for(int i = 0, _qsize = qsize(); i < _qsize; i++) {
                Node* cur = pop();
                if(dp[cur->n] < dist) continue;
                dp[cur->n] = dist;
                for(int near : adj[cur->n]) {
                    if(dp[near] < dist) continue;
                    if(near == endIdx) {
                        collectPath(wordList, cur, endIdx);
                        break;
                    }
                    if(isVisited(cur, near)) continue;
                    push(near, cur);
                }
            }
        }
        return ans;
    }
};