LeetCode: Alphabet Board Path

Posted on August 5, 2019July 26, 2020 by braindenny

Alphabet Board Path

Similar Problems:

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”], as shown in the diagram below.

We may make the following moves:

‘U’ moves our position up one row, if the position exists on the board;
‘D’ moves our position down one row, if the position exists on the board;
‘L’ moves our position left one column, if the position exists on the board;
‘R’ moves our position right one column, if the position exists on the board;
‘!’ adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: No need for hashmap

// https://code.dennyzhang.com/alphabet-board-path
// Basic Ideas: array
//
//  From character -> (x, y)
//  From (x1, y1) to (x2, y2)
//
//  Notice: how to avoid invalid moves?
//
//    Move: L
//    Move: U
//    Move: D
//    Move: R
//
// Complexity: Time O(n) Space O(1)
func moves(res *[]byte, cnt int, ch byte) {
    for i:=0; i<cnt; i++ {
        *res = append(*res, ch)
    }
}

func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}
func alphabetBoardPath(target string) string {
    res := []byte{}
    x, y := 0, 0
    for i, _ := range target {
        v := int(target[i]-'a')
        x2, y2 := v/5, v%5
        moves(&res, max(y-y2, 0), 'L')
        moves(&res, max(x-x2, 0), 'U')
        moves(&res, max(x2-x, 0), 'D')
        moves(&res, max(y2-y, 0), 'R')
        res = append(res, '!')
        x, y = x2, y2
    }
    return string(res)
}

// https://code.dennyzhang.com/alphabet-board-path
// Basic Ideas: hashmap
//
// Complexity: Time O(n) Space O(1)
func moveDirection(res *[]byte, offset int, move byte) {
    for i:=0; i<offset; i++ {
        *res = append(*res, move)
    }
}

func alphabetBoardPath(target string) string {
    chars := [26][2]int{}
    i, j := 0, 0
    for k:=0; k<26; k++ {
        if j == 5 {
            i++
            j=0
        }
        chars[k] = [2]int{i, j}
        j++
    }

    res := []byte{}
    i, j = 0, 0
    movex, movey := byte(' '), byte(' ')
    for k, _ := range target {
        ch := target[k]-'a'
        i2, j2 := chars[ch][0], chars[ch][1]
        offsetX, offsetY := i2-i, j2-j
        movex = 'D'
        if offsetX < 0 {
            movex, offsetX = 'U', -offsetX
        }
        // move at x direction
        movey = 'R'
        if offsetY < 0 {
            movey, offsetY = 'L', -offsetY
        }
        // Whether target is 'z'
        if target[k] == 'z' {
            // move y then z
            moveDirection(&res, offsetY, movey)
            moveDirection(&res, offsetX, movex)
        } else {
            moveDirection(&res, offsetX, movex)
            moveDirection(&res, offsetY, movey)
        }
        res = append(res, '!')
        i, j = i2, j2
    }
    return string(res)
}

Post Views: 0