12 ms concise C++ solution


  • 0
    G
        int findRotateSteps(string ring, string key) {
            int m = (int)ring.length(), n = (int)key.length();
            vector<vector<int>> indices(26, vector<int>());
            vector<pair<int, int>> prev, curr;
            for (int i = 0; i < m; ++i) {
                indices[ring[i] - 'a'].push_back(i);
                if (ring[i] == key[0]) {
                    prev.push_back({i, min(i, m - i) + 1});
                }
            }
            for (int i = 1; i < n; ++i) {
                for (int j : indices[key[i] - 'a']) {
                    pair<int, int> p1 = {j, INT_MAX};
                    for (auto& p2 : prev) {
                        int steps = min((p1.first - p2.first + m) % m, (p2.first - p1.first + m) % m);
                        p1.second = min(p1.second, p2.second + steps + 1);
                    }
                    curr.push_back(p1);
                }
                prev = curr;
                curr.clear();
            }
            int result = INT_MAX;
            for (auto& p : prev) {
                result = min(result, p.second);
            }
            return result;
        }
    

Log in to reply
 

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