C++ DFS+Memo 18 ms, DP 100 ms


  • 0
    V

    DP is C++ version of Java solution from this post by @shawngao.

    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        int dp[m + 1][n] = {};
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = INT_MAX;
                for (int k = 0; k < n; ++k) {
                    if (ring[k] == key[i]) {
                        int step = min(abs(j - k), n - abs(j - k));
                        dp[i][j] = min(dp[i][j], step + dp[i + 1][k]);
                    }
                }
            }
        }
        return dp[0][0] + m;
    } // 100 ms
    

    For DFS solution, I am creating an array of indexes for each letter, so that I can find closest letters on the dial in O(log n).

    int steps(int p1, int p2, int dSize) { return min(abs(p1 - p2), dSize - abs(p1 - p2)); }
    int findRotateSteps(string& key, int kPos, int dPos, int dSize, vector<vector<int>>& abcPos, vector<vector<int>>& memo) {
        if (kPos == key.size()) return 0;
        if (memo[dPos][kPos] != -1) return memo[dPos][kPos];
    
        auto chPos = abcPos[key[kPos] - 'a'];
        if (chPos.size() > 1) {
            auto it = lower_bound(chPos.begin(), chPos.end(), dPos);
            if (it == chPos.end()) it = chPos.begin();
            if (*it == dPos) 
                return memo[dPos][kPos] = findRotateSteps(key, kPos + 1, dPos, dSize, abcPos, memo);
            
            auto pos2 = it == chPos.begin() ? chPos[chPos.size() - 1] : *next(it, -1);
            return memo[dPos][kPos] = min(
                steps(dPos, *it, dSize) + findRotateSteps(key, kPos + 1, *it, dSize, abcPos, memo),
                steps(dPos, pos2, dSize) + findRotateSteps(key, kPos + 1, pos2, dSize, abcPos, memo)
            );
        }
        return memo[dPos][kPos] = steps(dPos, chPos[0], dSize) 
            + findRotateSteps(key, kPos + 1, chPos[0], dSize, abcPos, memo);
    }
    int findRotateSteps(string ring, string key) {
        vector<vector<int>> abcPos(26);
        vector<vector<int>> memo(ring.size(), vector<int>(key.size(), -1));
        for (auto i = 0; i < ring.size(); ++i) abcPos[ring[i] - 'a'].push_back(i);
        return findRotateSteps(key, 0, 0, ring.size(), abcPos, memo) + key.size();
    } // 18 ms
    

Log in to reply
 

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