Concise C++ Dp solution with explaination


  • 0
    S

    The base case is that dp[i][j] can be based on any valid dp[i-1][z] plus the min distance between z and j.

    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            vector<vector<int>> dp(key.size(),vector<int>(ring.size(),INT_MAX));
            //base case
            for(int i=0;i<ring.size();i++){
                if(key[0]==ring[i]){
                    dp[0][i]=min(i,(int)ring.size()-i);  //i is the distance the ring move to right, ring.size()-i is the ring move to left
                    dp[0][i]++;    //click button
                }
            }
    
             //general case
            for(int i=1;i<key.size();i++){
                for(int j=0;j<ring.size();j++){
                    if(key[i]==ring[j]){
                        for(int z=0;z<ring.size();z++){
                            if(dp[i-1][z]!=INT_MAX){
                                int distance= j>z?min(j-z,(int) (ring.size()-j+z)):min(z-j,(int)(ring.size()-z+j));   
                                dp[i][j]=min(dp[i][j],dp[i-1][z]+distance);
                            }
                        }
                        dp[i][j]++;
                    }
                }
            }
            int res=INT_MAX;
            for(int i=0;i<ring.size();i++){
                res=min(res,dp[key.size()-1][i]);
            }
            return res;
        }
    };
    
    

Log in to reply
 

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