aboutsummaryrefslogtreecommitdiff
path: root/alphabet_board_path.cpp
blob: 874e20181ba94ffec59b8b1c472061a9201f0c20 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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!
}