leetcode-go/hard/514.freedom-trail.go

func findRotateSteps(ring string, key string) int {
	// dp[i][j] means the min steps required to get the key[j] from ring[i],
	// then dp[0][0] is the answer.
	m, n := len(ring), len(key)
	if n == 0 {
		return 0
	}
	const INF int = 1e9
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n+1)
	} // dp[i][j] = min(dp[i][j], dist(i, k) + dp[k][j+1])
	for j := n - 1; 0 <= j; j-- {
		for i := 0; i < m; i++ {
			dp[i][j] = INF
			for k := 0; k < m; k++ {
				if ring[k] == key[j] {
					step := minInt(abs(k-i), m-abs(k-i))
					dp[i][j] = minInt(dp[i][j], step+dp[k][j+1])
				}
			}
		}
	}
	return dp[0][0] + n
}

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

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}