C++ O(n) space DP


  • 0
    G
    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            int n = ring.size();
            //indicies for each char in ring
            vector< vector<int> > indicies(128);
            for(int i = 0; i < n; i++)
                indicies[ ring[i] ].push_back(i);
            //dp vector: pair: <index, min steps>
            vector< pair<int, int> > cur = { make_pair(0, 0) };
            for(int i = 0; i < key.size(); i++){
                vector< pair<int, int> > next;
                for(int ind : indicies[ key[i] ] ){
                    int min = INT_MAX;
                    for(auto p : cur){
                        min = std::min( min, p.second + getDiff(p.first, ind, n) );
                    }
                    next.push_back( make_pair(ind, min + 1) );
                }
                cur = next;
            }
            int ans = INT_MAX;
            for(auto p : cur)
                ans = std::min(ans, p.second);
            return ans;
        }
        //get min steps between a and b given ring size n
        int getDiff(int a, int b, int n){
            return std::min( abs(a- b), n - abs(a - b) );
        }
    };
    

Log in to reply
 

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