1138. Alphabet Board Path

[Tcdian]

1138. Alphabet Board Path

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

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

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

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

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

Example 1

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints

• 1 <= target.length <= 100
• target consists only of English lowercase letters.

[Tcdian]

Solution ( DFS )

• Go Solution

func alphabetBoardPath(target string) string {
    board := []string{"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
    hash := make(map[byte]int);
    for i, s := range board {
        for j := 0; j < len(s); j++ {
            hash[s[j]] = i * 10 + j;
        }
    }
    result := "";
    prePosition := 0;
    for i := 0; i < len(target); i++ {
        targetPosition := hash[target[i]];
        prePositionX := prePosition / 10;
        prePositionY := prePosition % 10;
        targetPositionX := targetPosition / 10;
        targetPositionY := targetPosition % 10;
        verMove := "D";
        verDistance := targetPositionX - prePositionX;
        horMove := "R";
        horDistance := targetPositionY - prePositionY;
        if targetPositionX < prePositionX {
            verMove = "U";
            verDistance = prePositionX - targetPositionX;
        }
        if targetPositionY < prePositionY {
            horMove = "L";
            horDistance = prePositionY - targetPositionY;
        }

        if targetPosition == 50 {
            result += move(horMove, horDistance);
            result += move(verMove, verDistance);
        } else {
            result += move(verMove, verDistance);
            result += move(horMove, horDistance);
        }
        result += "!";
        prePosition = targetPosition;
    }
    return result;
}

func move(direction string, distance int) string {
    result := "";
    for i := 0; i < distance; i++ {
        result += direction;
    }
    return result;
}