1138. Alphabet Board Path

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.

Rust Solution

struct Solution;

impl Solution {
    fn alphabet_board_path(target: String) -> String {
        let mut pos: Vec<(i32, i32)> = vec![];
        for i in 0..5 {
            for j in 0..5 {
                pos.push((i, j));
            }
        }
        pos.push((5, 0));

        let mut v = vec!['a'];
        for c in target.chars() {
            v.push(c);
        }
        let n = v.len();
        let mut res = "".to_string();
        for i in 1..n {
            let curr = pos[(v[i] as u8 - b'a') as usize];
            let prev = pos[(v[i - 1] as u8 - b'a') as usize];
            let mut r = curr.0 - prev.0;
            let mut c = curr.1 - prev.1;
            while r < 0 {
                res.push('U');
                r += 1;
            }
            while c < 0 {
                res.push('L');
                c += 1;
            }
            while r > 0 {
                res.push('D');
                r -= 1;
            }
            while c > 0 {
                res.push('R');
                c -= 1;
            }
            res.push('!');
        }
        res
    }
}

#[test]
fn test() {
    let target = "leet".to_string();
    let res = "DDR!UURRR!!DDD!".to_string();
    assert_eq!(Solution::alphabet_board_path(target), res);
    let target = "code".to_string();
    let res = "RR!DDRR!UUL!R!".to_string();
    assert_eq!(Solution::alphabet_board_path(target), res);
}

Having problems with this solution? Click here to submit an issue on github.