题解首先将字母板上每个字符的位置存储到字典 char_dict 中,键为字符,值为其位置坐标 (行, 列)。然后,为了简化代码逻辑,将目标字符串 target 前加上字符 'a',表示从 'a' 开始的路径。接下来,遍历 target 的每个字符,计算从前一个字符到当前字符的行列位置差 diff。根据 diff 的值,生成对应的移动指令 ('U', 'D', 'L', 'R')。特别地,当目标字符是 'z' 时,先进行列移动再进行行移动,以避免移动到字母板外。每完成一个字符的定位,就添加 '!' 操作以收集字符。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def alphabetBoardPath(self, target):
board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"] # 字母板
char_dict = {} # 字符位置映射
for i in range(len(board)): # 构建映射表
for j in range(len(board[i])):
char_dict[board[i][j]] = (i, j)
target = 'a' + target # 从 'a' 开始
res = [] # 结果指令集
for i in range(1, len(target)): # 遍历 target
diff = [char_dict[target[i]][0] - char_dict[target[i - 1]][0], char_dict[target[i]][1] - char_dict[target[i - 1]][1]] # 行列差
if target[i] != 'z': # 如果当前字符不是 'z'
if diff[0] > 0:
res += diff[0] * ['D'] # 下移
elif diff[0] < 0:
res += -diff[0] * ['U'] # 上移
if diff[1] > 0:
res += diff[1] * ['R'] # 右移
elif diff[1] < 0:
res += -diff[1] * ['L'] # 左移
else: # 特殊处理字符 'z'
if diff[1] > 0:
res += diff[1] * ['R']
elif diff[1] < 0:
res += -diff[1] * ['L']
if diff[0] > 0:
res += diff[0] * ['D']
elif diff[0] < 0:
res += -diff[0] * ['U']
res.append('!') # 收集字符
return ''.join(res)