14. 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!"

Solution:

Approach: Find the position and direction and move Edge case:- Movement to 'z'

class Solution
{
public:
    string alphabetBoardPath(string target)
    {
        unordered_map<char, pair<int, int>> m;
        string res = "";

        int c = 0;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                char ch = c + 97;
                m[ch] = {i, j};
                c++;
            }
        }

        m[c + 97] = {5, 0};

        int x = 0, y = 0;

        for (int i = 0; i < target.length(); i++)
        {
            char ch = target[i];
            int pos1 = m[ch].first;
            int pos2 = m[ch].second;

            int d1 = pos1 - x;
            int d2 = pos2 - y;

            if (d1 == 0 && d2 == 0)
            {
                res += '!';
                continue;
            }

            if (ch == 'z')
            {
                d1--;
            }

            char xMove = (d1 >= 0) ? 'D' : 'U';
            char yMove = (d2 >= 0) ? 'R' : 'L';

            for (int i = 0; i < abs(d1); i++)
            {
                res += xMove;
            }

            for (int i = 0; i < abs(d2); i++)
            {
                res += yMove;
            }

            x = pos1;
            y = pos2;

            if (ch == 'z')
            {
                res += 'D';
                res += '!';
            }
            else
            {
                res += '!';
            }
        }

        return res;
    }
};