1138. 字母板上的路径

Medium

题目描述

在一个字母板上，我们从位置 (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 只包含英文小写字母。

解题思路

这道题需要在一个字母板上移动，从当前位置到目标字符位置，然后添加该字符到结果中。

解题思路：

建立字符到坐标的映射：首先需要确定每个字符在板上的位置。字母板是 6×5 的网格，除了最后一行只有字符 ‘z’。
计算移动路径：对于每个目标字符，计算从当前位置到目标位置需要的移动步数。移动分为水平和垂直两个方向。
特殊处理字符 ‘z’：由于 ‘z’ 在最后一行且只有一个位置 (5,0)，从其他位置到 ‘z’ 或从 ‘z’ 到其他位置时需要特别注意边界。
移动策略：
- 如果目标是 ‘z’：先向左移动到第0列，再向下移动
- 如果当前在 ‘z’ 位置：先向上移动，再向右移动
- 其他情况：可以直接按最短路径移动
生成移动序列：根据坐标差值生成对应的移动指令（‘U’、‘D’、‘L’、‘R’），最后添加 ‘!’ 表示选择当前字符。

这种方法确保了移动的有效性，避免了越界问题，特别是处理了字符 ‘z’ 的特殊情况。

代码实现

class Solution {
public:
    string alphabetBoardPath(string target) {
        vector<pair<int, int>> pos(26);
        for (int i = 0; i < 26; i++) {
            pos[i] = {i / 5, i % 5};
        }
        
        string result;
        int curRow = 0, curCol = 0;
        
        for (char c : target) {
            int targetRow = pos[c - 'a'].first;
            int targetCol = pos[c - 'a'].second;
            
            // 如果当前在z位置，先向上移动
            if (curRow == 5) {
                result += string(curRow - targetRow, 'U');
                curRow = targetRow;
            }
            
            // 水平移动
            if (targetCol < curCol) {
                result += string(curCol - targetCol, 'L');
            } else {
                result += string(targetCol - curCol, 'R');
            }
            curCol = targetCol;
            
            // 垂直移动
            if (targetRow < curRow) {
                result += string(curRow - targetRow, 'U');
            } else {
                result += string(targetRow - curRow, 'D');
            }
            curRow = targetRow;
            
            result += '!';
        }
        
        return result;
    }
};

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        pos = {}
        for i in range(26):
            pos[chr(ord('a') + i)] = (i // 5, i % 5)
        
        result = []
        cur_row, cur_col = 0, 0
        
        for c in target:
            target_row, target_col = pos[c]
            
            # 如果当前在z位置，先向上移动
            if cur_row == 5:
                result.append('U' * (cur_row - target_row))
                cur_row = target_row
            
            # 水平移动
            if target_col < cur_col:
                result.append('L' * (cur_col - target_col))
            else:
                result.append('R' * (target_col - cur_col))
            cur_col = target_col
            
            # 垂直移动
            if target_row < cur_row:
                result.append('U' * (cur_row - target_row))
            else:
                result.append('D' * (target_row - cur_row))
            cur_row = target_row
            
            result.append('!')
        
        return ''.join(result)

public class Solution {
    public string AlphabetBoardPath(string target) {
        var pos = new int[26][];
        for (int i = 0; i < 26; i++) {
            pos[i] = new int[] { i / 5, i % 5 };
        }
        
        var result = new StringBuilder();
        int curRow = 0, curCol = 0;
        
        foreach (char c in target) {
            int targetRow = pos[c - 'a'][0];
            int targetCol = pos[c - 'a'][1];
            
            // 如果当前在z位置，先向上移动
            if (curRow == 5) {
                result.Append(new string('U', curRow - targetRow));
                curRow = targetRow;
            }
            
            // 水平移动
            if (targetCol < curCol) {
                result.Append(new string('L', curCol - targetCol));
            } else {
                result.Append(new string('R', targetCol - curCol));
            }
            curCol = targetCol;
            
            // 垂直移动
            if (targetRow < curRow) {
                result.Append(new string('U', curRow - targetRow));
            } else {
                result.Append(new string('D', targetRow - curRow));
            }
            curRow = targetRow;
            
            result.Append('!');
        }
        
        return result.ToString();
    }
}

/**
 * @param {string} target
 * @return {string}
 */
var alphabetBoardPath = function(target) {
    const getPos = (char) => {
        const code = char.charCodeAt(0) - 97;
        return [Math.floor(code / 5), code % 5];
    };
    
    let result = '';
    let currPos = [0, 0];
    
    for (let char of target) {
        const [targetRow, targetCol] = getPos(char);
        const [currRow, currCol] = currPos;
        
        // Move left first if needed
        if (targetCol < currCol) {
            result += 'L'.repeat(currCol - targetCol);
        }
        
        // Move up if needed
        if (targetRow < currRow) {
            result += 'U'.repeat(currRow - targetRow);
        }
        
        // Move down if needed
        if (targetRow > currRow) {
            result += 'D'.repeat(targetRow - currRow);
        }
        
        // Move right if needed
        if (targetCol > currCol) {
            result += 'R'.repeat(targetCol - currCol);
        }
        
        result += '!';
        currPos = [targetRow, targetCol];
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	其中 n 是 target 的长度，需要遍历每个字符并生成对应的移动序列
空间复杂度	O(1)	除了结果字符串外，只使用常数额外空间存储字符位置映射

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析