41 lines
1.1 KiB
C#
41 lines
1.1 KiB
C#
|
public class Solution {
|
||
|
|
private int Steps(int x, int y, int mod) {
|
||
|
|
var distance = Math.Abs(x - y);
|
||
|
|
var coDistance = mod - distance;
|
||
|
|
return Math.Min(distance, coDistance);
|
||
|
|
}
|
||
|
|
|
||
|
|
private void Relax(string ring, string key, int[][] dp, int r, int k) {
|
||
|
|
for (var c = 0; c < ring.Length; ++c) {
|
||
|
|
if (ring[c] != key[k]) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
dp[r][k] = Math.Min(
|
||
|
|
dp[r][k],
|
||
|
|
1 + Steps(r, c, ring.Length) + dp[c][k + 1]
|
||
|
|
);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
public int FindRotateSteps(string ring, string key) {
|
||
|
|
var dp = new int[ring.Length][];
|
||
|
|
for (var i = 0; i < ring.Length; ++i) {
|
||
|
|
var ringPosition = new int[key.Length + 1];
|
||
|
|
|
||
|
|
Array.Fill(ringPosition, int.MaxValue);
|
||
|
|
ringPosition[key.Length] = 0;
|
||
|
|
|
||
|
|
dp[i] = ringPosition;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (var k = key.Length - 1; k >= 0; --k) {
|
||
|
|
for (var r = 0; r < ring.Length; ++r) {
|
||
|
|
Relax(ring, key, dp, r, k);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return dp[0][0];
|
||
|
|
}
|
||
|
|
}
|