C++ DP code


  • 0
    L

    class Solution {
    public:
    int findRotateSteps(string ring, string key) {
    if (key.size() == 0) return 0;
    vector<vector<int>> d(key.size() + 1, vector<int>(ring.size(), 1000000));
    d[0][0] = 0;
    for (int i = 0; i < key.size(); i++) {
    for (int j = 0; j < ring.size(); j++) {
    if (ring[j] == key[i]) {
    int t = 1000000;
    for (int k = 0; k < ring.size(); k++) {
    int temp = 1000000;
    int n = ring.size();
    temp = min(temp, (k - j + n) % n);
    temp = min(temp, (j - k + n) % n);
    t = min(t, temp + d[i][k]);
    }
    d[i+1][j] = t + 1;
    }
    }
    }
    int ans = 1000000;
    for (int i = 0; i < ring.size(); i++) ans = min(ans, d[key.size()][i]);
    return ans;
    }
    };


Log in to reply
 

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