Share my graph bfs travel solution


  • -1
    S
    // a graph whose two nodes of one edge just differ one character
    // bread first search to get the shortest distance from start to end
    // time complexity: O(min(26^L, sizs(dic))
    // the worsest time is check all the characters in dict
    // or one string whose characters check all 26 characters
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if (start.size() == 0 || end.size() == 0 || dict.size() == 0) 
            return 0;
        
        unordered_set<string> hs; hs.insert(end);
        queue<string> q; q.push(end);
        
        int dis = 1;
        int lastNum = 1, curNum = 0;
        
        while (!q.empty()) {
            string str = q.front();
            q.pop();
            lastNum--;
            
            for (int i = 0; i < str.size(); ++i) {
                for (char j = 'a'; j <= 'z'; ++j) {
                    if (j == str[i]) continue;
                    char t = str[i]; 
                    str[i] = j;
                    if (str == start) return dis+1;
                    if (dict.count(str) && hs.count(str) == 0) {
                        curNum++;
                        q.push(str);
                        hs.insert(str);
                    }
                    str[i] = t;
                }
            }
            
            if (lastNum == 0) {
                lastNum = curNum;
                curNum = 0;
                dis++;
            }
        }
        
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.