aboutsummaryrefslogtreecommitdiff
path: root/alphabet_board_path.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'alphabet_board_path.cpp')
-rw-r--r--alphabet_board_path.cpp44
1 files changed, 44 insertions, 0 deletions
diff --git a/alphabet_board_path.cpp b/alphabet_board_path.cpp
new file mode 100644
index 0000000..874e201
--- /dev/null
+++ b/alphabet_board_path.cpp
@@ -0,0 +1,44 @@
+// 1138. Alphabet Board Path
+#include "leetcode.h"
+
+/*
+ * on an alphabet board, we start position [0,0], corresponding to character
+ * 'board[0][0]'. here, 'board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy",
+ * "z"]' as show in the diagram (see page). return a sequence of moves that
+ * makes our answer equal to 'target' in the minimum numbe of moves. (in any
+ * order/path)
+ */
+
+class Solution {
+public:
+ string alphabetBoardPath(string target) {
+ unordered_map<char, pair<int, int>> mp;
+ for (int i = 0; i < 26; ++i)
+ mp[i + 'a'] = {i / 5, i % 5};
+ target = 'a' + target;
+ string path;
+ int dx = 0, dy = 0;
+ for (int i = 1; i < target.size(); ++i) {
+ auto curr = mp[target[i]];
+ auto prev = mp[target[i - 1]];
+ dx = curr.first - prev.first;
+ dy = curr.second - prev.second;
+ if (dy < 0)
+ path += string(-dy, 'L');
+ if (dx < 0)
+ path += string(-dx, 'U');
+ if (dy > 0)
+ path += string(dy, 'R');
+ if (dx > 0)
+ path += string(dx, 'D');
+ path += '!';
+ }
+ return path;
+ }
+};
+
+int main() {
+ Solution boj;
+ cout << boj.alphabetBoardPath("leet") << endl; // expect: DDR!UURRR!!DDD!
+ cout << boj.alphabetBoardPath("code") << endl; // expect: RR!DDRR!UUL!R!
+}