On an alphabet board, we start at position (0, 0)
, corresponding to character board[0][0]
.
Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]
.
We may make the following moves:
'U'
moves our position up one row, if the square exists;'D'
moves our position down one row, if the square exists;'L'
moves our position left one column, if the square exists;'R'
moves our position right one column, if the square exists;'!'
adds the character board[r][c]
at our current position (r, c)
to the answer.
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.
题目大意:
给出一个由字母排列成的矩阵,给出一个target,并且给出可以在矩阵中移动规则,从起始位置(0,0)出发经过最短的操作输出target。(注意,操作不能超出矩阵的范围)
解题思路:
首先考虑搜索,题目中给出上下左右操作就说明,可以来利用字母在矩阵中的坐标直接进行计算。
下一个字母的坐标-上一个字母的坐标,其x和y正负对应了上下左右操作,计算差值即可。
另外要注意若末位置为z则,不能首末位置直接相减。因为会超出边界,则我们可以将末位置先设为u,然后在结果中插入D即可。
class Solution {
public:
string alphabetBoardPath(string target) {
vector<vector<int>> maps;
for(int i=0;i<26;i++){
vector<int> tmp_maps;
tmp_maps.push_back(i/5);
tmp_maps.push_back(i%5);
maps.push_back(tmp_maps);
}
string ans="";
int idx = 0, idy =0;
for(int i=0;i<target.length();i++){
int x = maps[target[i]-'a'][0];
int y = maps[target[i]-'a'][1];
int d_x = x - idx;
int d_y = y - idy;
if(d_x == 0 && d_y == 0){
ans = ans + '!';
}else{
if(target[i] == 'z'){
d_x--;
}
int tt;
if(d_x<0){
tt = d_x * -1;
while(tt--){
ans = ans + 'U';
}
}else{
tt = d_x;
while(tt--){
ans = ans + 'D';
}
}
if(d_y<0){
tt = d_y * -1;
while(tt--){
ans = ans + 'L';
}
}else{
tt = d_y;
while(tt--){
ans = ans + 'R';
}
}
if(target[i] == 'z'){
ans = ans +'D';
}
ans = ans + '!';
}
idx = x;
idy = y;
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)