clean C++ solution with DP


  • 0
    J
    class Solution {
    private:
        int help(string& ring, string& key, int k, int curr, vector<vector<int>>& record, unordered_map<char,vector<int>>& h) {
            if (record[k][curr]>=0)
                return record[k][curr];
            char ch = key[k];
            int n = ring.length();
            int m = key.length();
            int res = -1;
            for (auto i:h[ch]) {
                int left = curr - i;
                if (left<0)
                    left+=n;
                int right = i - curr;
                if (right<0) 
                    right+=n;
                int shift = min(left,right);
                if (res<0) {
                    if (k+1<m)
                        res = shift + help(ring,key,k+1,i,record,h);
                    else 
                        res = shift;
                } else {
                    if (k+1<m)
                        res = min(res,shift + help(ring,key,k+1,i,record,h));
                    else
                        res = min(res,shift);
                }
            }
            record[k][curr] = res;
            return res;
        }
    public:
        int findRotateSteps(string ring, string key) {
            int m = key.length();
            int n = ring.length();
            unordered_map<char,vector<int>> h;
            for (int i=0;i<n;++i) {
                h[ring[i]].push_back(i);
            }
            vector<vector<int>> record(m,vector<int>(n,-1));
            return m+help(ring,key,0,0,record,h);
        }
    };
    

Log in to reply
 

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