[LeetCode Word Ladder II]

题意：给出一个初始字符串S和目标字符串T，以及可行的中间字符串集合dict，转换字符串时仅允许一次改变一个字符，要求从S变为T的所有最短可行序列。

分析：首先，需要枚举每个字符串可行的改变方式，并用BFS建图：建立结点编号对可达字符串的映射关系，并记录每个结点的深度。建图结束后，用深搜的方式枚举出所有可行的字符串，剪枝方案只简单记录了无效结点。最后跑出的时间是1096 ms。

vector<vector<string> > vvs;
vector<string> vs;
map<string, int> Msi;
map<int, string> Mis;
int hd[100000], el, si, ti, sl, d[100000];
char b[100000];

struct E
{
    int v, p;
}e[100000];

void adde(int u, int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

void bfs(string s, string t, unordered_set<string> &dict)
{
    int i, j, k, l, u, v;
    queue<string> Q;
    d[si]=0;
    Msi[s]=si++;
    Mis[0]=s;
    Q.push(s);
    while(!Q.empty())
    {
        s=Q.front(); Q.pop();
        u=Msi[s];
        for(i=0; i<sl; i++)
        {
            k=s[i];
            for(j='a'; j<='z'; j++)
            {
                if(j==k)
                    continue;
                s[i]=j;
                if(dict.find(s)==dict.end())
                    continue;
                if(Msi.find(s)!=Msi.end())
                {
                    v=Msi[s];
                    if(d[v]==d[u]+1)
                        adde(u, v);
                    continue;
                }
                v=Msi[s]=si++;
                d[v]=d[u]+1;
                Mis[v]=s;
                Q.push(s);
                adde(u, v);
            }
            s[i]=k;
        }
    }
}

int dfs(int u, int vsl)
{
    if(b[u]||vsl>d[ti])
        return b[u]=1;
    int l, v;
    if(vs.size()<=vsl)
        vs.push_back(Mis[u]);
    else
        vs[vsl]=Mis[u];
    if(u==ti)
    {
        vvs.push_back(vs);
        return 0;
    }
    b[u]=1;
    for(l=hd[u]; l!=-1; l=e[l].p)
    {
        v=e[l].v;
        if(!dfs(v, vsl+1))
            b[u]=0;
    }
    return b[u];
}

class Solution {
public:
    vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {
        dict.insert(t);
        vvs.clear();
        vs.clear();
        Msi.clear();
        Mis.clear();
        memset(hd, -1, sizeof hd);
        memset(b, 0, sizeof b);
        si=el=0;
        sl=s.length();
        bfs(s, t, dict);
        if(Msi.find(t)==Msi.end())
            return vvs;
        ti=Msi[t];
        dfs(0, 0);
        return vvs;
    }
};

100

101

vector<vector<string> > vvs;

vector<string> vs;

map<string, int> Msi;

map<int, string> Mis;

int hd[100000], el, si, ti, sl, d[100000];

char b[100000];

struct E

{

int v, p;

}e[100000];

void adde(int u, int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

void bfs(string s, string t, unordered_set<string> &dict)

{

int i, j, k, l, u, v;

queue<string> Q;

d[si]=0;

Msi[s]=si++;

Mis[0]=s;

Q.push(s);

while(!Q.empty())

{

s=Q.front(); Q.pop();

u=Msi[s];

for(i=0; i<sl; i++)

{

k=s[i];

for(j='a'; j<='z'; j++)

{

if(j==k)

continue;

s[i]=j;

if(dict.find(s)==dict.end())

continue;

if(Msi.find(s)!=Msi.end())

{

v=Msi[s];

if(d[v]==d[u]+1)

adde(u, v);

continue;

}

v=Msi[s]=si++;

d[v]=d[u]+1;

Mis[v]=s;

Q.push(s);

adde(u, v);

}

s[i]=k;

}

int dfs(int u, int vsl)

{

if(b[u]||vsl>d[ti])

return b[u]=1;

int l, v;

if(vs.size()<=vsl)

vs.push_back(Mis[u]);

else

vs[vsl]=Mis[u];

if(u==ti)

{

vvs.push_back(vs);

return 0;

}

b[u]=1;

for(l=hd[u]; l!=-1; l=e[l].p)

{

v=e[l].v;

if(!dfs(v, vsl+1))

b[u]=0;

}

return b[u];

}

class Solution {

public:

vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {

dict.insert(t);

vvs.clear();

vs.clear();

Msi.clear();

Mis.clear();

memset(hd, -1, sizeof hd);

memset(b, 0, sizeof b);

si=el=0;

sl=s.length();

bfs(s, t, dict);

if(Msi.find(t)==Msi.end())

return vvs;

ti=Msi[t];

dfs(0, 0);

return vvs;

}

};

ps：不得不说LeetCode做题好刺激，每题都不给数据范围，并且debug非常困难，基本就是各种靠猜。这题整整交了48次才过，实在是太多的血与泪。