C++_DP_Space: O(n), Time: O(r*r*k)


  • 0
    class Solution {
    public:
    int findRotateSteps(string ring, string key) {
        unordered_map<int,vector<int>> mp;
        for(int i = 0; i < ring.size(); ++i){
            mp[ring[i]].push_back(i);
        }
        int n = ring.size();
        int m = key.size();
        int r_len = ring.size();
        vector<int> dp(n, INT_MAX);
        for(auto j : mp[key[0]]){
            dp[j] = min(j, r_len - j);
        }
        //dp[j]:the minimized steps needed from start to j where j is the current position at Ring,  if our current position in Key is k.
        int res = INT_MAX;
        for(int k = 1; k < m; ++k){
            vector<int> tmp(n, INT_MAX);
            vector<int> curPos = mp[key[k]];//The positions we need to calculate for current position at k in Key.
            for(auto cur : curPos){
                for(int j = 0; j < n; ++j){
                    if(dp[j] < INT_MAX){
                        tmp[cur] = min(tmp[cur], dp[j] + min(abs(cur - j), r_len - abs(cur - j)));
                    }
                }
            }
            dp = tmp;
        }
        for(auto num : dp){
            res = min(res, num);
        }
        return res + key.size();
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.