C++ DP


  • 0
    T

    Similar to travel optimization.

    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            map<char,vector<int>> m;
            for (int i=0; i<ring.size();i++)
                m[ring[i]].push_back(i);
            
            vector<pair<int, int>> sk;
            sk.push_back(make_pair(0,0));
            for (auto&& c: key)
            {
                map<int, int> im;
                for(auto&& pre: sk)
                {
                    for (auto&&b :m[c])
                    {
                        int temp=pre.second+min(abs(b-pre.first),(int)ring.size()-abs(b-pre.first))+1;
                        if (im.count(b))
                            im[b]=min(im[b], temp);
                        else
                            im[b]=temp;
                    }
                }
                sk.clear();
                for (auto& mt:im) sk.push_back(make_pair(mt.first, mt.second));
            }
            
            int res=INT_MAX;
            for (auto&& x: sk)
                res=min(res, x.second);
                
            return res;
    
        }
    };
    

Log in to reply
 

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