C语言 | Leetcode C语言题解之第514题自由之路

题目：

题解：

int findRotateSteps(char* ring, char* key) {
    int n = strlen(ring), m = strlen(key);
    int pos[26][n], posSize[26];
    memset(posSize, 0, sizeof(posSize));
    for (int i = 0; i < n; ++i) {
        int x = ring[i] - 'a';
        pos[x][posSize[x]++] = i;
    }
    int dp[m][n];
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    for (int i = 0; i < posSize[key[0] - 'a']; i++) {
        int x = pos[key[0] - 'a'][i];
        dp[0][x] = fmin(x, n - x) + 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < posSize[key[i] - 'a']; ++j) {
            int x = pos[key[i] - 'a'][j];
            for (int k = 0; k < posSize[key[i - 1] - 'a']; ++k) {
                int y = pos[key[i - 1] - 'a'][k];
                dp[i][x] = fmin(dp[i][x], dp[i - 1][y] + fmin(abs(x - y), n - abs(x - y)) + 1);
            }
        }
    }
    int ret = dp[m - 1][0];
    for (int i = 1; i < n; ++i) {
        ret = fmin(ret, dp[m - 1][i]);
    }
    return ret;
}