复习一下，防止复试被问到 class Solution { public: int findRotateSteps(string ring, string key) { int m = key.size(), n = ring.size(); vector<vector<int>> pos(26, vector<int>(0, 0)); for (int i = 0; i < n; i++) { pos[ring[i] - 'a'].push_back(i); } vector<vector<int>> dp(m, vector<int>(n, 0x3f3f3f3f)); for (auto j:pos[key[0] - 'a']) { dp[0][j] = min(j, n - j); } for (int i = 1; i < m; i++) { for (auto j:pos[key[i] - 'a']) { for (auto k:pos[key[i - 1] - 'a']) { dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(k - j), n - abs(k - j))); } } } int min = INT_MAX; for (auto item:dp[m - 1]) { if (item < min) { min = item; } } return min + m; } };