On an alphabet board, we start at position (0, 0), corresponding to character&nbsp;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;
	'!'&nbsp;adds the character board[r][c] at our current position (r, c)&nbsp;to the&nbsp;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&nbsp;in the minimum number of moves.&nbsp; You may return any path that does so.

&nbsp;
Example 1:
Input: target = "leet"
Output: "DDR!UURRR!!DDD!"
Example 2:
Input: target = "code"
Output: "RR!DDRR!UUL!R!"

&nbsp;
Constraints:


	1 &lt;= target.length &lt;= 100
	target consists only of English lowercase letters.

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        def shortestPath(r,c,tr,tc):
            path = ""
            pr = r
            while r > tr:
                path += 'U'
                r -= 1
            while r < tr:
                path += 'D'
                r += 1
            if tr == 5 and pr != tr: path = path[:len(path) - 1]
            while c > tc:
                path += 'L'
                c -= 1
            while c < tc:
                path += 'R'
                c += 1
            if tr == 5 and pr != tr: path = path + 'D'
            return path

        table = ['abcde','fghij','klmno','pqrst','uvwxy','z']
        r,c = 0,0
        ans = ""
        for character in target:
            t_row = None
            for i,word in enumerate(table):
                if character in word:
                    t_row = i
                    break
            t_col = table[i].index(character)
            ans += shortestPath(r,c,t_row,t_col) + '!'
            r,c = t_row,t_col
        return ans
class Solution {
    public String alphabetBoardPath(String target) {
        int x = 0, y = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < target.length(); i++){
            char ch = target.charAt(i);
            int x1 = (ch - 'a') / 5;
            int y1 = (ch - 'a') % 5;
            while(x1 < x)   {x--; sb.append('U');}
            while(y1 > y)   {y++; sb.append('R');}
            while(y1 < y)   {y--; sb.append('L');}
            while(x1 > x)   {x++; sb.append('D');}
            sb.append('!');
        }
        return sb.toString();
    }
}
class Solution {
public:
    string alphabetBoardPath(string target) {
        string ans = "";
        int prevRow = 0;
        int prevCol = 0;
        int curRow = 0;
        int curCol = 0;
        for(int i = 0; i < target.length(); i++){
            prevCol = curCol;
            prevRow = curRow;
            curRow = (target[i] - 'a')/5;
            curCol = (target[i] - 'a')%5;
            if(curRow == 5 and abs(curCol - prevCol) > 0){
                curRow--;
            }
            if(curRow - prevRow > 0){
                ans += string((curRow - prevRow), 'D');
            }else{
                ans += string((prevRow - curRow), 'U');
            }
            if(curCol - prevCol > 0){
                ans += string((curCol - prevCol), 'R');
            }else{
                ans += string((prevCol - curCol), 'L');
            }
            if(((target[i] - 'a')/5) == 5 and abs(curCol - prevCol) > 0){
                ans += 'D';
                curRow++;
            }
            ans += '!';
        }
        return ans;

    }
};
var alphabetBoardPath = function(target) {
    var result = "";
    var list = "abcdefghijklmnopqrstuvwxyz";
    var curr = 0;
    for(i=0;i<target.length;i++){ 
          let next = list.indexOf(target[i]);
          if(next!==curr){   
              if(curr===25) curr-=5, result+="U";
              if(next%5!==curr%5){  
                 diff = next%5-curr%5;
                 if(diff>0) curr+=diff, result+="R".repeat(diff);
                 else curr+=diff, result+="L".repeat(-diff);  
             }
             diff = (next-curr)/5;
             if(diff>0) curr+=diff*5, result+="D".repeat(diff);
             else curr+=diff*5, result+="U".repeat(-diff);     
          }
    result+='!';
    }
    return result;
};
Alphabet Board Path