题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为 board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]。

我们可以按下面的指令规则行动：

• 如果方格存在，'U' 意味着将我们的位置上移一行；
• 如果方格存在，'D' 意味着将我们的位置下移一行；
• 如果方格存在，'L' 意味着将我们的位置左移一列；
• 如果方格存在，'R' 意味着将我们的位置右移一列；
• '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

样例

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

输入：target = "code"
输出："RR!DDRR!UUL!R!"

限制

• 1 <= target.length <= 100
• target 仅含有小写英文字母。

算法

(模拟) $O(ans.length)$

1. 先用哈希表记录下每个字母所在的坐标。
2. 移动时，首先判断是否需要向左移动，然后再判断上下移动，最后判断向右移动。这是因为 z 这个字母比较特殊，向 z 走时需要先向左移动，从 z 出发时，需要先向上移动。

时间复杂度

• 时间复杂度为答案的长度。

空间复杂度

• 仅需要一个空间为 26 的哈希表，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    string calc(const pair<int, int> &p1, const pair<int, int> &p2) {
        int x = p2.first - p1.first;
        int y = p2.second - p1.second;
        string ret;

        if (y < 0)
            ret += string(-y, 'L');

        if (x < 0)
            ret += string(-x, 'U');

        if (x > 0)
            ret += string(x, 'D');

        if (y > 0)
            ret += string(y, 'R');

        return ret;
    }

    string alphabetBoardPath(string target) {
        unordered_map<char, pair<int, int>> pos;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                pos['a' + i * 5 + j] = make_pair(i, j);
        pos['z'] = make_pair(5, 0);

        pair<int, int> cur(0, 0);
        string ans;
        for (auto &c : target) {
            ans += calc(cur, pos[c]);
            cur = pos[c];
            ans += "!";
        }
        return ans;
    }
};