leetcode127 单词接龙

题目

单词接龙

分析

分析同leetcode433 最小基因变化

代码

class Solution {
private:
    unordered_set<string> st;

    bool find_end(string& str, string& end, queue<string>& que) {

        for (int m = 0; m < str.size(); m++) {
            string new_str = str;
            for (char ch = 'a'; ch <= 'z'; ch++) {
                new_str[m] = ch;
                if (new_str == end) {
                    return true;
                }
                if (st.count(new_str)) {
                    que.push(new_str);
                    st.erase(new_str);
                }
            }            
        }

        return false;
    }
public:
    int ladderLength(string start, string end, vector<string>& bank) {
        st = unordered_set<string>(bank.begin(), bank.end());

        if (st.count(end) == 0) {
            return 0;
        }

        queue<string> que;
        que.push(start);
        if (st.count(start)) {
            st.erase(start);
        }
        int res = 0;

        while (!que.empty()) {
            res++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                string str = que.front();
                que.pop();

                if (find_end(str, end, que)) {
                    return res + 1;
                } 
            }
        }

        return 0;
    }
};