Question

1138. 字母板上的路径

English Version

题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，'U' 意味着将我们的位置上移一行；
• 如果方格存在，'D' 意味着将我们的位置下移一行；
• 如果方格存在，'L' 意味着将我们的位置左移一列；
• 如果方格存在，'R' 意味着将我们的位置右移一列；
• '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

 

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

 

提示：

• 1 <= target.length <= 100
• target 仅含有小写英文字母。

解法

方法一：模拟

从起点 $(0, 0)$ 出发，模拟每一步的移动，将每一步的移动结果拼接到答案中。注意移动的方向遵循“左、上、右、下”的顺序。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $target$ 的长度，需要遍历字符串 $target$ 中的每一个字符。忽略答案的空间消耗，空间复杂度 $O(1)$。

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)

class Solution {
  public String alphabetBoardPath(String target) {
    StringBuilder ans = new StringBuilder();
    int i = 0, j = 0;
    for (int k = 0; k < target.length(); ++k) {
      int v = target.charAt(k) - 'a';
      int x = v / 5, y = v % 5;
      while (j > y) {
        --j;
        ans.append('L');
      }
      while (i > x) {
        --i;
        ans.append('U');
      }
      while (j < y) {
        ++j;
        ans.append('R');
      }
      while (i < x) {
        ++i;
        ans.append('D');
      }
      ans.append("!");
    }
    return ans.toString();
  }
}

class Solution {
public:
  string alphabetBoardPath(string target) {
    string ans;
    int i = 0, j = 0;
    for (char& c : target) {
      int v = c - 'a';
      int x = v / 5, y = v % 5;
      while (j > y) {
        --j;
        ans += 'L';
      }
      while (i > x) {
        --i;
        ans += 'U';
      }
      while (j < y) {
        ++j;
        ans += 'R';
      }
      while (i < x) {
        ++i;
        ans += 'D';
      }
      ans += '!';
    }
    return ans;
  }
};

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)
}