宽度优先搜索+存储路径。一直在做的就是优化时间。用map优化到1500ms好感动。

struct NodeString {
    vector&lt;NodeString <em>&gt; before;
    string now;
};
class Solution {
public:
    vector&lt;vector&lt;string&gt;&gt;result;
     vector&lt;vector&lt;string&gt;&gt; findLadders(string start, string end, unordered_set&lt;string&gt; &amp;dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        result.clear();
         if(dict.find(start) == dict.end()) {
            dict.insert(start);
        }
        if(dict.find(end) == dict.end()) {
            dict.insert(end);
        }
        map&lt;string,NodeString *&gt;maps;
        maps.clear();
        maps.insert(map&lt;string,NodeString *&gt;::value_type(start,NULL));
        vector&lt;NodeString</em>&gt;strs,strsc;
        strs.clear();
        NodeString * nodeString = new NodeString();
        nodeString-&gt;before.clear();
        nodeString-&gt;now = start;
        strs.push_back(nodeString);
        bool isFind = false;
        while(true) {
            map&lt;string,NodeString *&gt;mapstmp;
            mapstmp.clear();
            strsc.clear();
            for(int i = 0;i &lt; strs.size();i++) {
                string item = strs[i]-&gt;now;
                for(int j = 0;j &lt; item.length();j++) {
                    for(char c = 'a';c &lt;= 'z';c++) {
                        string tmp = item;<br />
                        if(c != item[j]) {
                            tmp[j] = c;
                            if(dict.find(tmp) != dict.end()) {
                                if(maps.find(tmp) == maps.end()) {
                                    NodeString * nodetmp = new NodeString();
                                    nodetmp-&gt;before.clear();
                                    nodetmp-&gt;before.push_back(strs[i]);
                                    nodetmp-&gt;now = tmp;
                                    if(tmp == end) {
                                        isFind = true;
                                        vector&lt;string&gt;items;
                                        items.clear();
                                        //items.push_back(end);
                                        genResult(nodetmp,items);
                                        continue;
                                    }
                                    strsc.push_back(nodetmp);<br />
                                    maps.insert(map&lt;string,NodeString *&gt;::value_type(tmp,nodetmp));
                                    mapstmp.insert(map&lt;string,NodeString *&gt;::value_type(tmp,nodetmp));
                                }
                                else {
                                    if(tmp != start) {
                                        map&lt;string,NodeString *&gt;::iterator it = mapstmp.find(tmp);
                                        if(it != mapstmp.end())
                                            it-&gt;second-&gt;before.push_back(strs[i]);
                                    }
                                }
                            }
                        }
                    }
                }
            }</p>

<pre><code>        if(strsc.size() == 0 || isFind)break;
        strs.clear();
        for(int i = 0;i &amp;lt; strsc.size();i++) {
            strs.push_back(strsc[i]);
        }
    }
    return result;
}
</code></pre>

<p>private:
    void genResult(NodeString * nodeString,vector&lt;string&gt;&amp;items) {
        if(nodeString-&gt;before.size() == 0) {
            items.push_back(nodeString-&gt;now);
            vector&lt;string&gt;itemsr;
            itemsr.clear();
            vector&lt;string&gt;::reverse_iterator rit;
            for(rit = items.rbegin();rit != items.rend();rit++) {
                itemsr.push_back(*rit);
            }
            result.push_back(itemsr);
            items.pop_back();
        }
        else {
            for(int i = 0;i &lt; nodeString-&gt;before.size();i++) {
                items.push_back(nodeString-&gt;now);
                genResult(nodeString-&gt;before[i],items);
                items.pop_back();
            }
        }
    }
};