CPP 22ms DP solution


  • 1
    S
    class Solution {
        vector<vector<int>> dp;
    public:
        int findRotateSteps(string ring, string key) {
            if (key.empty()) return 0;
            int keyLen = key.length(), ringLen = ring.length();
            
            dp = vector<vector<int>>(keyLen, vector<int>(ringLen, -1));
            
            for (int i = 0; i < ringLen; i++) {
                if (ring[i] == key[0]) {
                    dp[0][i] = min(i, ringLen - i) + 1;
                }
            }
            
            for (int i = 1; i < keyLen; i++) {
                for (int j = 0; j < ringLen; j++) {
                    if (ring[j] == key[i]) {
                        int step = INT_MAX;
                        for (int k = 0; k < ringLen; k++) {
                            if (dp[i - 1][k] >= 0) {
                                int t = abs(k - j);
                                step = min(step, min(t, ringLen - t) + 1 + dp[i - 1][k]);
                            }
                        }
                        dp[i][j] = step;
                    }
                }
            }
            
            int minStep = INT_MAX;
            for (int i = 0; i < ringLen; i++) {
                if (dp[keyLen - 1][i] >= 0) {
                    minStep = min(minStep, dp[keyLen - 1][i]);
                }
            }
            
            return minStep;
        }
    };
    

Log in to reply
 

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