1138. 字母板上的路径-526互联

方法：模拟

解题思路

为了使得移动次数最小，每次移动方式为，"直角移动"（如下图），但由于 \(z\) 字母位置的特殊性，当其作为目标字母和当前字母时，为了避免越界问题，需要调整 \(x\) 和 \(y\) 方向上移动的顺序。
无标题.png

代码

class Solution {
public:
    string alphabetBoardPath(string target) {
        string ans;
        int last_x = 0, last_y = 0; // 记录当前字母的坐标
        for (char ch : target) {
            int x = (ch - 'a') / 5, y = (ch - 'a') % 5; // 目标字母的坐标
            int move_x = abs(last_x - x), move_y = abs(last_y - y); // 记录x 和 y方向上需要移动的距离
            string str_x(move_x, last_x < x ? 'D' : 'U'); // x 方向上移动的序列
            string str_y(move_y, last_y < y ? 'R' : 'L'); // y 方向上移动的序列
            ans += (ch == 'z' ? str_y + str_x : str_x + str_y) + '!'; // 当目标字母为z时，先左右走(x方向)；当目标字母不为z时，当前字母可能为z，先上下走(y方向)，这样可以避免越界
            last_x = x;
            last_y = y;
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)，\(n\) 为 \(target\) 字母串的长度；
空间复杂度：\(O(1)\)，除了返回值外，未使用其他空间。

postorder traversal 1138