[LeetCode]Word Ladder 最短距离字符串转换 (Dijkstra)

要求最短距离。采纳dijkstra查找节点之间的最短路径。

当心：假设是一个枚举字典22是否元素可以，如果转换，暂停。

提高：每串，带您历数它的字符值事件，对于的长度n一个字符串枚举n*26次要。

设仅仅是简单的枚举，则会出现重边：

如abc,bbc,cbc，建图后每两个节点间均有两条双向边，这对于邻接表存储的图会存在非常多冗余边。

解决方法：每一个节点每位字符仅仅能从原始字符往后枚举，即

枚举各字符串第一位的话

abc：bbc,cbc,dbc,...

bbc：cbc,dbc,...

cbc：dbc,....

struct Edge{

    int v,next;

};

class Solution {

public:

	Edge*e;

    int *head,len,n;

    void addedge(int u,int v){

        e[len].v=v;

        e[len].next=head[u];

        head[u]=len++;

        e[len].v=u;

        e[len].next=head[v];

        head[v]=len++;

    }

    bool canTrans(const string& p,const string&q){

        int i,cnt=0;

        for(i=0;i<p.size();++i){

            if(p[i]!=q[i]){

                cnt++;

                if(cnt>1)return 0;

            }

        }

        return 1;

    }

    int dijk(int st,int ed){

        int* dist=new int[n],i,v,j,k;

        memset(dist,127,sizeof(int)*n);

		int unre=dist[0];

        for(i=head[st];i!=-1;i=e[i].next){

            v=e[i].v;

            dist[v]=1;

        }

        dist[st]=-1;

        for(j=1;j<n;++j){

            for(i=0,k=-1;i<n;++i)

                if(dist[i]>0&&dist[i]!=unre&&(k<0||dist[i]<dist[k]))

                    k=i;

            if(k<0||k==ed)break;

            for(i=head[k];i!=-1;i=e[i].next){

                v=e[i].v;

                if(dist[v]>=0&&dist[v]>dist[k]+1)

                    dist[v]=dist[k]+1;

            }

            dist[k]=-1;

        }

        if(k==ed)

            k=dist[k];

        else k=-1;

        delete[]dist;

        return k;

    }

    int ladderLength(string start, string end, unordered_set<string> &dict) {

        if(start==end)return 2;

        map<string,int>mp;

        int cnt=0,i;

        mp[start]=cnt++;

        mp[end]=cnt++;

        unordered_set<string>::iterator bg=dict.begin(),ed=dict.end(),bg2;

        for(;bg!=ed;bg++){

            if(mp.find(*bg)==mp.end())

                mp[*bg]=cnt++;

        }

        dict.insert(start);

        dict.insert(end);

		n=dict.size();

        e=new Edge[n*n];

        head=new int[n];

		len=0;

		memset(head,-1,sizeof(int)*n);

		int ch,j;

        for(bg=dict.begin(),ed=dict.end();bg!=ed;bg++){

            string s=*bg;

            for(i=0;i<s.length();++i){

                ch=s[i]-'a';

                for(j=ch+1;j<26;++j){

                    s[i]='a'+j;

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

                        addedge(mp[s],mp[*bg]);

                }

                s[i]='a'+ch;

            }

     /*       for(bg2=bg,bg2++;bg2!=ed;bg2++){

                if(canTrans(*bg,*bg2)){

                    addedge(mp[*bg],mp[*bg2]);

                }

            }*/

        }

        i=dijk(mp[start],mp[end]);

		delete[] e;

		delete[]head;

        return i>=0?i+1:0;

    }

};