[leetcode] wordladder ii

problem: https://oj.leetcode.com/problems/word-ladder-ii/
代码：https://play.golang.org/p/qdmadQUcEC

package main

import (
    "fmt"
)

func main() {
    start := "hit"
    end := "cog"
    dict := []string{"hot","dot","dog","lot","log"}
    dict = append(dict,start,end)

    mapAdjacency := createAdjacencyGraph(dict,end)
    findLadders(mapAdjacency,end)
}

func findLadders(mapAdjacency map[string][]string,end string) {
    visited := make(map[string]int,len(mapAdjacency))
    visited[start] = 1

    queue := make([]string,len(mapAdjacency))
    queue = append(queue,start)

    mapParent := make(map[string][]string,len(mapAdjacency))

    bfs(mapAdjacency,visited,queue,mapParent,end)

    stack := []string{}
    stack = append(stack,end)
    printShortestPath(mapParent,stack,end)
}

func printShortestPath(mapParent map[string][]string,stack []string,end string) {
    if end == start {
        printStack(stack)
        return
    }

    for _,v := range mapParent[end] {
        stack = append(stack,v)
        printShortestPath(mapParent,v)
        stack = stack[:len(stack)-1]
    }
}

func printStack(stack []string) {
    lenStack := len(stack)
    for i := lenStack - 1; i >= 0; i-- {
        fmt.Printf("%s ",stack[i])
    }
    fmt.Println()
}

func bfs(mapAdjacency map[string][]string,visited map[string]int,queue []string,mapParent map[string][]string,start string,end string) {
    var cur string
    for len(queue) > 0 {
        //出队列
        cur,queue = queue[0],queue[1:]
        for _,value := range mapAdjacency[cur] {
            if visited[value] == 0 {
                //入队列
                queue = append(queue,value)
                visited[value] = visited[cur] + 1
                mapParent[value] = append(mapParent[value],cur)
            } else if visited[value] > visited[cur] {
                mapParent[value] = append(mapParent[value],cur)
            }

        }
    }

}

func createAdjacencyGraph(dict []string,end string) (mapAdjacency map[string][]string) {
    mapAdjacency = make(map[string][]string)
    lenWord := len(start)
    for _,vi := range dict {
        for _,vj := range dict {
            count := 0
            if vi != vj {
                for k := 0; k < lenWord; k++ {
                    if vi[k] == vj[k] {
                        count++
                    }
                }
                if count == lenWord-1 { //find adjacency
                    mapAdjacency[vi] = append(mapAdjacency[vi],vj)
                }
            }

        }
    }

    return
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!