Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1138.html

1138. Alphabet Board Path

Level

Medium

Description

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.

Solution

Obtain all letters’ positions. For each pair of adjacent letters, obtain the path by the difference between the two positions’ rows and the difference between the two positions’ columns. When each letter is to be typed, add the path from the previous position to the current position to the sequence, and add '!' to the sequence.

If the current letter or the previous letter is z, then the path needs to be obtained differently. Since z is only letter in the last row, it is impossible to move left in the last row to reach z, and it is also impossible to move right in the last row from z. Therefore, to move to z, first move left to the leftmost column then move down. To move from z, first move up then move right (if the next letter is not in the leftmost column).

Finally, return the sequence.

• Java
• C++
• Python
• Go

• class Solution {
      public String alphabetBoardPath(String target) {
          StringBuffer sequence = new StringBuffer();
          int length = target.length();
          int[][] positions = new int[length][2];
          for (int i = 0; i < length; i++) {
              int[] position = position(target.charAt(i));
              positions[i][0] = position[0];
              positions[i][1] = position[1];
          }
          if (target.charAt(0) != 'a') {
              int[] start = {0, 0};
              String path0 = path(start, positions[0]);
              sequence.append(path0);
          }
          sequence.append("!");
          for (int i = 1; i < length; i++) {
              int[] prevPosition = positions[i - 1];
              int[] curPosition = positions[i];
              String path = path(prevPosition, curPosition);
              sequence.append(path);
              sequence.append("!");
          }
          return sequence.toString();
      }
  
      public int[] position(char letter) {
          int number = letter - 'a';
          int row = number / 5;
          int column = number % 5;
          int[] position = {row, column};
          return position;
      }
  
      public String path(int[] position1, int[] position2) {
          int row1 = position1[0], column1 = position1[1], row2 = position2[0], column2 = position2[1];
          if (row1 == row2 && column1 == column2)
              return "";
          StringBuffer path = new StringBuffer();
          if (row1 == 5 && column1 == 0) {
              for (int i = row1; i > row2; i--)
                  path.append("U");
              for (int i = column1; i < column2; i++)
                  path.append("R");
          } else if (row2 == 5 && column2 == 0) {
              for (int i = column1; i > column2; i--)
                  path.append("L");
              for (int i = row1; i < row2; i++)
                  path.append("D");
          } else {
              for (int i = row1; i > row2; i--)
                  path.append("U");
              for (int i = row1; i < row2; i++)
                  path.append("D");
              for (int i = column1; i > column2; i--)
                  path.append("L");
              for (int i = column1; i < column2; i++)
                  path.append("R");
          }
          return path.toString();
      }
  }
  

• // OJ: https://leetcode.com/problems/alphabet-board-path/
  // 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;
      }
  };
  

• class Solution:
      def alphabetBoardPath(self, target: str) -> str:
          i = j = 0
          ans = []
          for c in target:
              v = ord(c) - ord("a")
              x, y = v // 5, v % 5
              while j > y:
                  j -= 1
                  ans.append("L")
              while i > x:
                  i -= 1
                  ans.append("U")
              while j < y:
                  j += 1
                  ans.append("R")
              while i < x:
                  i += 1
                  ans.append("D")
              ans.append("!")
          return "".join(ans)
  
  ############
  
  # 1138. Alphabet Board Path
  # https://leetcode.com/problems/alphabet-board-path/
  
  class Solution:
      def alphabetBoardPath(self, target: str) -> str:
          res, i, j = "", 0, 0
          
          for t in target:
              v = ord(t) - ord('a')
              ti, tj = v // 5, v % 5
              
              if ti == i and tj == j:
                  res += "!"
              else:
                  if ti != i:
                      if ti >= i:
                          if ti == 5 and j != 0:
                              res += "D" * (ti - i - 1)
                          else:
                              res += "D" * (ti - i)
                      else:
                          res += "U" * (i - ti)
  
                  if tj != j:
                      if tj >= j:
                          res += "R" * (tj - j)
                      else:
                          res += "L" * (j - tj)
                      
                      if ti == 5:
                          res += "D"
                      
                  res += "!"
                  
              i, j = ti, tj
          
          return res
          
  
  

• func alphabetBoardPath(target string) string {
  	ans := []byte{}
  	var i, j int
  	for _, c := range target {
  		v := int(c - 'a')
  		x, y := v/5, v%5
  		for j > y {
  			j--
  			ans = append(ans, 'L')
  		}
  		for i > x {
  			i--
  			ans = append(ans, 'U')
  		}
  		for j < y {
  			j++
  			ans = append(ans, 'R')
  		}
  		for i < x {
  			i++
  			ans = append(ans, 'D')
  		}
  		ans = append(ans, '!')
  	}
  	return string(ans)
  }
  

All Problems

All Solutions