Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

Note:

Return 0 if there is no such transformation sequence.

思路：1） Graph的BFS问题 一种是显式的构造Graph 第二种是直接搜索，不进行构造 注意两种情况都可能有TLE

class Solution {
public:
    bool is_ajacent(const string & a, const string & b){
        if (a.size() != b.size()){
            return false;
        }
        int k = 0;
        for(size_t i = 0; i < a.size() && k <= 2; i++){
            if (a.at(i) != b.at(i)){
                k++;
            }
        }
        return k == 1;
    }
    int bfs(string start, string end, unordered_set<string> &dict){
        if (start == end){
            return 0;
        }

        m_visit.insert(start);
        queue<pair<string, int> > qu;
        qu.push(make_pair(start,1));

        while(!qu.empty()){
            pair<string,int> current = qu.front();
            qu.pop();

            //Small Judge Pass but large Judge TLE
            //Optimization : 1) can we delete it?
            //Optimization : 2) 当前的for循环太耗时了，复杂度是 (N + N^2 + N^3 ....+N^N)*M
            //正确的分析是：假设每一个Node的出度是K，那么应该是 (K^0 + K^1 + K^2 +....+K^N) *M  所以K很多N很大会TLE

            //那么双向BFS是否也会TLE呢？
            //考虑 current.first的元素变换 长度M 最后复杂度是：  M*26*N

            /*
            for(unordered_set<string>::iterator iter = dict.begin(); iter != dict.end(); iter++){
                if (m_visit.find(*iter) == m_visit.end() && is_ajacent(current.first,*iter)){ // no visit
                    if (*iter == end){       //have found
                        return current.second + 1;
                    }
                    m_visit.insert(*iter);
                    qu.push(make_pair(*iter,current.second + 1));
                }
            }*/

            //优化版本在Large Judge上AC

            for(size_t i = 0; i < current.first.size(); i++){
                string ex = current.first;
                for(int j = 'a'; j <= 'z'; j++){
                    if (ex[i] == j){
                        continue;
                    }
                    ex[i] = j;
                    if (dict.find(ex) != dict.end() && m_visit.find(ex) == m_visit.end()){
                        if (ex == end){       //have found
                            return current.second + 1;
                        }
                        m_visit.insert(ex);
                        qu.push(make_pair(ex,current.second + 1));
                    }
                }
            }
        }
        if (dict.find(start) != dict.end() && dict.find(end) != dict.end()){ //"hot", "dog", ["hot","dog"] expect=0
            return 0;
        }
        return -1;
    }
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!dict.size()){
            return 0;
        }
        m_visit.clear();
        return bfs(start,end,dict);
    }
    unordered_set<string> m_visit;
};

class Solution {
public:
    struct Node{
        string value;
        int depth;

        Node(const string & value, int depth){
            this->value = value;
            this->depth = depth;
        }
    };
    struct Graph{
        public:
            Graph(){

            }
            ~Graph(){

            }
            bool constructGraph(unordered_set<string> &dict){
                unordered_set<string>::iterator i;
                unordered_set<string>::iterator j;

                if (dict.size() == 1){
                    vector<string> line;
                    matrix.insert(make_pair(*(dict.begin()),line));
                    return true;
                }

                for(i = dict.begin(); i != dict.end(); i++){
                    for(j = dict.begin(); j != dict.end(); j++){
                        if (*i == *j){
                            continue;
                        }
                        if (isLinked(*i,*j)){
                            addEdge(*i,*j);
                        }
                    }
                }

                return true;
            }
            bool addEdge(const string & start, const string & end){
                m_iter = matrix.find(start);
                if (m_iter == matrix.end()){
                    vector<string> line;
                    line.push_back(end);
                    matrix.insert(make_pair(start,line));
                }else{
                    m_iter->second.push_back(end);
                }
            }
            vector<string> & getEdges(const string & node){
                m_iter = matrix.find(node);
                return m_iter->second;
            }
            #define VISITED 1
            #define UNVISITED 0
            int BFS(const string & start, const string & end){
                map<string,int> v_map;
                for(m_iter = matrix.begin(); m_iter != matrix.end(); m_iter++){
                    //v_map[m_iter->fist] = UNVISITED;
                    v_map.insert(make_pair(m_iter->first,UNVISITED));
                }


                vector<string> edges;
                vector<string>::iterator v_iter;
                queue<Node> s;
                s.push(Node(start,1));

                while(!s.empty()){

                    Node node = s.front();
                    s.pop();

                    edges = getEdges(node.value);

                    for(v_iter = edges.begin(); v_iter != edges.end(); v_iter++){
                        if (v_map[*v_iter] == UNVISITED){
                            if (*v_iter == end){
                                return node.depth + 1;
                            }
                            s.push(Node(*v_iter,node.depth+1));
                        }
                    }
                    v_map[node.value] = VISITED;
                }
                return -1;
            }
            bool isLinked(const string & a, const string & b){
                if (a.size() != b.size()){
                    return false;
                }

                int diff = 0;
                for(size_t i = 0;i < a.size(); i++){
                    if (a.at(i) != b.at(i)){
                        diff++;
                    }
                }
                if (1 == diff){
                    return true;
                }
                return false;
            }
        private:
            vector<string>::iterator v_iter;
            map<string,vector<string>>::iterator m_iter;
            map<string,vector<string>> matrix;
    };
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        Graph graph;
        graph.constructGraph(dict);

        return graph.BFS(start,end);

    }
};

We must remember that there some bug in above code, since 11/16 unitest can pass.

原文链接: https://www.cnblogs.com/kwill/archive/2013/02/15/2913042.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍