## 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.