[C++知识库]leetcode1138. 字母板上的路径

leetcode1138. 字母板上的路径

1. 题目

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

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

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

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

示例 1：
输入：target = “leet”
输出：“DDR!UURRR!!DDD!”

示例 2：
输入：target = “code”
输出：“RR!DDRR!UUL!R!”

2. 解答

// 每次行动最大步数为8.

#define ALL_SIZE     1000
#define SIGLE_SIZE   9

int CalcSinglePath(char *temp, char target, char preChar)
{
    int preRow, afterRow, preCol, afterCol;
    char *leftOright = "LR";
    char *upOdown = "UD";

    preRow = (preChar - 'a') / 5;
    afterRow = (target - 'a') / 5;
    preCol = (preChar - 'a') % 5;
    afterCol = (target - 'a') % 5;

    int upDown = (preRow < afterRow) ? 1 : 0;
    int leftRight = (preCol < afterCol) ? 1 : 0;
    int row = abs(preRow - afterRow);
    int col = abs(preCol - afterCol);

    if (target == 'z') {
        row--;
    }

    for (int i = 0; i < row; i++) {
        temp[i] = upOdown[upDown];
    }
    for (int i = row; i < row + col; i++) {
        temp[i] = leftOright[leftRight];
    }
    if (target == 'z') {
        temp[row + col] = 'D';
        row++;
    }

    return row + col;
}

char * alphabetBoardPath(char * target) {
    char *result = (char *)malloc(sizeof(char) * ALL_SIZE);
    char preChar = 'a';
    int len = 0;

    for (int i = 0; i < strlen(target); i++) {
        if (i > 0 && target[i] == target[i - 1]) {
            result[len++] = '!';
            continue;
        }
        char *temp = (char *)malloc(sizeof(char) * SIGLE_SIZE);
        int tmp_len = CalcSinglePath(temp, target[i], preChar);
        memcpy(result + len, temp, tmp_len);
        preChar = target[i];
        len += tmp_len;
        result[len++] = '!';
    }
    result[len] = '\0';
    return result;
}