func findRotateSteps(s, t string) int {
n, m := len(s), len(t)
// 先算出每个字母的最后一次出现的下标
// 由于 s 是环形的，循环结束后的 pos 就刚好是 left[0]
pos := [26]int{} // 初始值不重要
for i, b := range s {
pos[b-'a'] = i
}
// 计算每个 s[i] 左边 a-z 的最近下标（左边没有就从 n-1 往左找）
left := make([][26]int, n)
for i, b := range s {
left[i] = pos
pos[b-'a'] = i // 更新下标
}
// 先算出每个字母的首次出现的下标
// 由于 s 是环形的，循环结束后的 pos 就刚好是 right[n-1]
for i := n - 1; i >= 0; i-- {
pos[s[i]-'a'] = i
}
// 计算每个 s[i] 右边 a-z 的最近下标（左边没有就从 0 往右找）
right := make([][26]int, n)
for i := n - 1; i >= 0; i-- {
right[i] = pos
pos[s[i]-'a'] = i // 更新下标
}
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n)
}
for j := m - 1; j >= 0; j-- {
for i := 0; i < n; i++ {
if s[i] == t[j] { // 无需旋转
f[j][i] = f[j+1][i]
continue
}
// 左边最近 or 右边最近，取最小值
l := left[i][t[j]-'a']
res1 := f[j+1][l]
if l > i {
res1 += n - l + i
} else {
res1 += i - l
}
r := right[i][t[j]-'a']
res2 := f[j+1][r]
if r < i {
res2 += n - i + r
} else {
res2 += r - i
}
f[j][i] = min(res1, res2)
}
}
return f[0][0] + m
}
class Solution:
def findRotateSteps(self, s: str, t: str) -> int:
s = [ord(c) - ord('a') for c in s]
t = [ord(c) - ord('a') for c in t]
n, m = len(s), len(t)
# 先算出每个字母的最后一次出现的下标
# 由于 s 是环形的，循环结束后的 pos 就刚好是 left[0]
pos = [0] * 26 # 初始值不重要
for i, c in enumerate(s):
pos[c] = i
# 计算每个 s[i] 左边 a-z 的最近下标（左边没有就从 n-1 往左找）
left = [None] * n
for i, c in enumerate(s):
left[i] = pos[:]
pos[c] = i # 更新下标
# 先算出每个字母的首次出现的下标
# 由于 s 是环形的，循环结束后的 pos 就刚好是 right[n-1]
for i in range(n - 1, -1, -1):
pos[s[i]] = i
# 计算每个 s[i] 右边 a-z 的最近下标（左边没有就从 0 往右找）
right = [None] * n
for i in range(n - 1, -1, -1):
right[i] = pos[:]
pos[s[i]] = i # 更新下标
f = [[0] * n for _ in range(m + 1)]
for j in range(m - 1, -1, -1):
c = t[j]
for i, x in enumerate(s):
if x == c: # 无需旋转
f[j][i] = f[j + 1][i]
else: # 左边最近 or 右边最近，取最小值
l, r = left[i][c], right[i][c]
f[j][i] = min(f[j + 1][l] + (n - l + i if l > i else i - l),
f[j + 1][r] + (n - i + r if r < i else r - i))
return f[0][0] + m
'''
定义 dp[i][j] 表示从前往后拼写出 key 的第 i 个字符，
ring 的第 j 个字符与 12:00 方向对齐的最少步数（下标均从 0 开始）。
'''
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n, m = len(ring), len(key)
pos = [[] for _ in range(26)]
for i, c in enumerate(ring):
pos[ord(c)-ord('a')].append(i)
dp = [[inf for i in range(n)] for _ in range(m)]
for p in pos[ord(key[0])-ord('a')]:
dp[0][p] = min(p, n-p) + 1
for i in range(1, m):
for j in pos[ord(key[i])-ord('a')]:
for k in pos[ord(key[i-1])-ord('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])
from collections import defaultdict as d
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
Choices = d() # 把每个key对应的可选的ring的字母的index做成字典。
for k in key:
if k in Choices:
continue
else:
Choices[k] = []
for ri, r in enumerate(ring):
if r == k:
Choices[k].append(ri)
counter = [{0 : 0}]
Path = d()
for keyi in range(len(key)): # 一共len(key)个格子。
counter.append({})
for choice in Choices[key[keyi]]: # choice是个index，是表示对于在key上第keyi个字母来说，ring里有哪几个位置的字母可以选择。
temp = []
for start in counter[keyi].keys(): # start表示上一个格子里，有几种情况可以到达当前的choice。
previous_distance = counter[keyi][start]
s = str(start) + "-" + str(choice)
if s not in Path:
d1 = abs(choice - start)
d2 = abs(len(ring) - d1)
newc = min(d1, d2)
Path[s] = newc
temp.append(previous_distance + Path[s])
counter[keyi + 1][choice] = min(temp) + 1 # 只需要保留最小值 再加1表示按下按钮。
# print(Choices)
final = min(counter[-1].values())
return final
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
}
class Solution {
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();
List<Integer>[] pos = new List[26];
for (int i = 0; i < 26; ++i) {
pos[i] = new ArrayList<Integer>();
}
for (int i = 0; i < n; ++i) {
pos[ring.charAt(i) - 'a'].add(i);
}
int[][] dp = new int[m][n];
for (int i = 0; i < m; ++i) {
Arrays.fill(dp[i], 0x3f3f3f);
}
for (int i : pos[key.charAt(0) - 'a']) {
dp[0][i] = Math.min(i, n - i) + 1;
}
for (int i = 1; i < m; ++i) {
for (int j : pos[key.charAt(i) - 'a']) {
for (int k : pos[key.charAt(i - 1) - 'a']) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
}
}
}
return Arrays.stream(dp[m - 1]).min().getAsInt();
}
}
