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

• 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
``````

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