当前位置：首页 > article >正文

Golang | Leetcode Golang题解之第514题自由之路

article 2024/11/1 5:38:06

题目：

题解：

func findRotateSteps(ring string, key string) int {
    const inf = math.MaxInt64 / 2
    n, m := len(ring), len(key)
    pos := [26][]int{}
    for i, c := range ring {
        pos[c-'a'] = append(pos[c-'a'], i)
    }
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = inf
        }
    }
    for _, p := range pos[key[0]-'a'] {
        dp[0][p] = min(p, n-p) + 1
    }
    for i := 1; i < m; i++ {
        for _, j := range pos[key[i]-'a'] {
            for _, k := range pos[key[i-1]-'a'] {
                dp[i][j] = min(dp[i][j], dp[i-1][k]+min(abs(j-k), n-abs(j-k))+1)
            }
        }
    }
    return min(dp[m-1]...)
}

func min(a ...int) int {
    res := a[0]
    for _, v := range a[1:] {
        if v < res {
            res = v
        }
    }
    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

查看全文

http://www.kler.cn/a/373987.html