aboutsummaryrefslogtreecommitdiff
path: root/freedom_trail.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-10 18:16:11 -0600
committerJack Sangdahl <[email protected]>2024-09-10 18:16:11 -0600
commit04058b633ddcf3858445bada106bbbc030cc6aac (patch)
treea2e033ec217a49ff5ac48e5e0105630ea7e54159 /freedom_trail.c
parent309241c48abc953042965d0735e17f098c426105 (diff)
downloadleetcode-04058b633ddcf3858445bada106bbbc030cc6aac.tar.gz
leetcode-04058b633ddcf3858445bada106bbbc030cc6aac.zip
514. freedom trail
Diffstat (limited to 'freedom_trail.c')
-rw-r--r--freedom_trail.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/freedom_trail.c b/freedom_trail.c
new file mode 100644
index 0000000..b9f1eb7
--- /dev/null
+++ b/freedom_trail.c
@@ -0,0 +1,53 @@
+// 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]'
+ */
+
+int dp[101][101];
+
+int dfs(char *ring, char *key, int ring_size, int key_size, int ring_idx,
+ int key_idx) {
+ if (key_idx == key_size)
+ return 0;
+ if (dp[key_idx][ring_idx] != -1)
+ return dp[key_idx][ring_idx];
+ int min_step = 1e9;
+ for (int i = 0; i < ring_size; i++)
+ if (ring[i] == key[key_idx]) {
+ int cw = (ring_idx + ring_size - i) % ring_size;
+ int ccw = (i + ring_size - ring_idx) % ring_size;
+ int step = fmin(cw, ccw) + 1 +
+ dfs(ring, key, ring_size, key_size, i, key_idx + 1);
+ min_step = fmin(min_step, step);
+ }
+ dp[key_idx][ring_idx] = min_step;
+ return min_step;
+}
+
+int findRotateSteps(char *ring, char *key) {
+ int ring_size = strlen(ring);
+ int key_size = strlen(key);
+ memset(dp, -1, sizeof(dp));
+ return dfs(ring, key, ring_size, key_size, 0, 0);
+}
+
+int main() {
+ char *r1 = "godding", *k1 = "gd", *r2 = "godding", *k2 = "godding";
+ printf("%d\n", findRotateSteps(r1, k1)); // expect: 4
+ printf("%d\n", findRotateSteps(r2, k2)); // expect: 13
+}