# Reference Code

`class Solution {    public:    vector<string> words;    int dis(int i, int j){        int ret = 0;        for (int k = 0; k < words[i].size(); ++k){            ret += words[i][k] != words[j][k];        }        return ret;    }    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        wordList.push_back(beginWord);        unordered_set<string> s(wordList.begin(), wordList.end());        if (s.find(endWord) == s.end()) return {};        vector<string> words(s.begin(), s.end());        unordered_map<string, vector<string>> graph;        const int n = words.size();        this -> words = words;        // Build graph        for (int i = 0; i < n - 1; ++i){            for (int j = i + 1; j < n; ++j){                if (dis(i, j) == 1){                    graph[words[i]].push_back(words[j]);                    graph[words[j]].push_back(words[i]);                }            }        }        vector<vector<string>> ret;        // BFS        int shortestLevel = INT_MAX;        vector<vector<string>> currentLevel;        currentLevel.push_back({beginWord});        int level = 1;        unordered_set<string> seen;        seen.insert(beginWord);        while (!currentLevel.empty()){            vector<vector<string>> newLevel;            // keep a this seen for this level and add those seen members after the traverse of this level as we may visit the same element multiple times only if they are on the same level.            unordered_set<string> thisseen;            for (auto words: currentLevel){                for (auto nei: graph[words.back()]){                    vector<string> newWords = words;                    if (seen.find(nei) != seen.end()) {                        continue;                    }                    if (nei == endWord && level + 1 <= shortestLevel){newWords.push_back(nei);                        ret.push_back(newWords);                        shortestLevel = level + 1;                     } else if (nei != endWord && level + 1 < shortestLevel){                        newWords.push_back(nei);                        newLevel.push_back(newWords);                        thisseen.insert(nei);                    }                }}            for (auto word: thisseen) seen.insert(word);            level++;            currentLevel = newLevel;        }        return ret;       }};`
`Runtime: 84 ms, faster than 13.20% of C++ online submissions for Word Ladder II.Memory Usage: 20.9 MB, less than 14.77% of C++ online submissions for Word Ladder II.`

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi