python using reachability matrix


  • 0
    H
    class Solution(object):
        def minMutation(self, start, end, bank):
            bank.append(start)
            n=len(bank)
            target=-1
            s=1
            for i in range(n):
                for j in range(8):
                    if end[j]!=bank[i][j]:
                        s=0
                        break
                if s==1:
                    target=i
                    break
                s=1
            if target==-1:
                return -1
            st=[]
            if n==1:
                return 0
            for i in range(n):
                st.append([0]*n)
            for i in range(n):
                for j in range(n):
                    different=0
                    for k in range(8):
                        if bank[i][k]!=bank[j][k]:
                            different+=1
                    if different==1:
                        st[i][j]=1
            s=st[n-1]
            for i in range(n-1):
                if s[target]!=0:
                    return i+1
                sta=[]
                for j in range(n):
                    t=0
                    for k in range(n):
                        t+=s[k]*st[k][j]
                    sta.append(t)
                s=sta
            return -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.