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 characterboard[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.
Solution: Manhattan walk
Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.
Time complexity: O(26*26 + n)
Space complexity: O(26*26)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: string alphabetBoardPath(string target) { vector<vector<string>> paths(26, vector<string>(26)); for (int s = 0; s < 26; ++s) for (int t = 0; t < 26; ++t) { int dx = t % 5 - s % 5; int dy = t / 5 - s / 5; string path; while (dx < 0) { path.push_back('L'); dx++; } while (dy < 0) { path.push_back('U'); dy++; } while (dx > 0) { path.push_back('R'); dx--; } while (dy > 0) { path.push_back('D'); dy--; } paths[s][t] = path; } char l = 'a'; string ans; for (char c : target) { ans += paths[l - 'a'][c - 'a'] + "!"; l = c; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment