aboutsummaryrefslogtreecommitdiff
path: root/other/freedom_trail.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/freedom_trail.cpp')
-rw-r--r--other/freedom_trail.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/other/freedom_trail.cpp b/other/freedom_trail.cpp
new file mode 100644
index 0000000..2763f8c
--- /dev/null
+++ b/other/freedom_trail.cpp
@@ -0,0 +1,55 @@
+// 514. Freedom Trail
+#include "leetcode.h"
+
+/*
+ * in the video game fallout 4, the quest "road to freeom" requires players to
+ * reach a metal dial call the "freedom trail ring" and use the dial to spell a
+ * specific keyword to open the door. given a string 'rint' that represents the
+ * code engraved on the outer ring and another string 'key' that represents the
+ * keyword that needs to be spelled, return the minimum number of steps to spell
+ * all of the characters in the keyword. initially, the first character of the
+ * ring is aligned at "12:00" diretion. you should spell all the characters in
+ * 'key' one by rotating 'ring' clockwise or anticlockwise to make each
+ * character of the string aligned at the "12:00" direction and then by pressing
+ * the center button. at the stage of rotating the ring to spell the key
+ * character 'key[i]' you can rotate the ring clockwise or anticlockwise by one
+ * place, which counts as one step. the final purpose of the rotation is to
+ * align one of 'ring's characters at "12:00" direction, where this character
+ * must equal 'key[i]'
+ */
+
+class Solution {
+public:
+ int findRotateSteps(string ring, string key) {
+ int n = ring.size();
+ unordered_map<char, vector<int>> idx_map;
+ for (int i = 0; i < n; ++i)
+ idx_map[ring[i]].push_back(i);
+ vector<vector<pair<int, int>>> dp(key.size());
+ for (int i : idx_map[key[0]]) {
+ int dist = min(i, n - i);
+ dp[0].push_back({i, dist});
+ }
+ int min_sum = INT_MAX;
+ for (int i = 1; i < key.size(); ++i) {
+ for (int idx : idx_map[key[i]]) {
+ int min_dist = INT_MAX;
+ for (auto &pair : dp[i - 1]) {
+ int abs_dist = abs(pair.first - idx);
+ int dist = min(abs_dist, n - abs_dist);
+ min_dist = min(min_dist, dist + pair.second);
+ }
+ dp[i].push_back({idx, min_dist});
+ if (i == key.size() - 1)
+ min_sum = min(min_dist, min_sum);
+ }
+ }
+ return min_sum + key.size();
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.findRotateSteps("godding", "gd")); // expect: 4
+ printf("%d\n", obj.findRotateSteps("godding", "godding")); // expect: 13
+}