1138. Alphabet Board Path

1138. Alphabet Board Path (Medium)

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.

Companies:
Google, Amazon

Related Topics:
Hash Table, String

Solution 1.

// OJ: https://leetcode.com/problems/alphabet-board-path/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string alphabetBoardPath(string target) {
        int x = 0, y = 0;
        string ans;
        for (char c : target) {
            int p = (c - 'a') / 5, q = (c - 'a') % 5;
            while (x != p || y != q) {
                if (q >= y) {
                    if (p > x) {
                        ++x;
                        ans += 'D';
                    } else if (p < x) {
                        --x;
                        ans += 'U';
                    } else {
                        ++y;
                        ans += 'R';
                    }
                } else {
                    --y;
                    ans += 'L';
                }
            }
            ans += '!';
        }
        return ans;
    }
};