Alphabet Board Path - Leetcode Solution

Problem Statement: On an alphabet board, we start at position (0, 0), corresponding to character board[0][0]. Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]. 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.

Our goal in this problem is to generate the alphabet board target of length target.length().

Solution: The solution can be achieved with the help of following steps:

1. Create a hash map that contains all the positions (r, c) of the characters on the alphabet board.
2. Loop through the target string and calculate the (r, c) position of the character.
3. Calculate the distance (number of moves) of the current position to the target character's position and add the appropriate movement steps to the answer string.
4. Add '!' to the answer string to indicate we have reached the target character.
5. Repeat steps 2-4 until we have reached the end of the target string.

The code for the same can be written as:

class Solution {
    public String alphabetBoardPath(String target) {
        Map<Character, int[]> map = new HashMap<>();
        String[] board = {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
        
        // Populating the Hash Map
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length(); j++){
                map.put(board[i].charAt(j), new int[]{i, j});
            }
        }
        
        int[] cur = new int[]{0, 0}; // Current position
        StringBuilder sb = new StringBuilder(); // Answer String
        
        // Looping through the target string
        for(char ch : target.toCharArray()){
            int[] targetPos = map.get(ch);
            int rowDiff = targetPos[0] - cur[0];
            int colDiff = targetPos[1] - cur[1];
            
            // Performing appropriate movements
            if(rowDiff > 0){
                while(rowDiff-- > 0) sb.append('D');
            }
            if(colDiff > 0){
                while(colDiff-- > 0) sb.append('R');
            }
            if(rowDiff < 0){
                while(rowDiff++ < 0) sb.append('U');
            }
            if(colDiff < 0){
                while(colDiff++ < 0) sb.append('L');
            }
            
            sb.append('!'); // Adding '!' to indicate we have reached the target character
            cur = targetPos; // Updating the current position
        }
        return sb.toString(); // Returning the answer string
    }
}

Time Complexity: O(n), where n is the length of the target string. Space Complexity: O(1), as the hash map size is constant and independent of input size.

1The problem can be found here: https://leetcode.com/problems/alphabet-board-path/
2
3#include <iostream>
4#include <vector>
5#include <string>
6
7using namespace std;
8
9class Solution {
10public:
11    string alphabetBoardPath(string target) {
12        // your code here
13        vector<vector<char>> board = {{'a','b','c','d','e'},
14                                     {'f','g','h','i','j'},
15                                     {'k','l','m','n','o'},
16                                     {'p','q','r','s','t'},
17                                     {'u','v','w','x','y'},
18                                     {'z'}};
19        int x = 0, y = 0;
20        string res = "";
21        for(int i = 0; i < target.size(); i++){
22            int cur_x = 0, cur_y = 0;
23            for(int j = 0; j < board.size(); j++){
24                for(int k = 0; k < board[j].size(); k++){
25                    if(target[i] == board[j][k]){
26                        cur_x = j;
27                        cur_y = k;
28                    }
29                }
30            }
31            if(cur_x > x){
32                for(int j = 0; j < cur_x - x; j++){
33                    res += "D";
34                }
35            }
36            else if(cur_x < x){
37                for(int j = 0; j < x - cur_x; j++){
38                    res += "U";
39                }
40            }
41            if(cur_y > y){
42                for(int j = 0; j < cur_y - y; j++){
43                    res += "R";
44                }
45            }
46            else if(cur_y < y){
47                for(int j = 0; j < y - cur_y; j++){
48                    res += "L";
49                }
50            }
51            res += "!";
52            x = cur_x;
53            y = cur_y;
54        }
55        return res;
56    }
57};