[Swift]LeetCode1138.字母板上的路径|AlphabetBoardPath

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

我们从一块字母板上的位置 (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 仅含有小写英文字母。

Runtime: 4 ms

Memory Usage: 20.3 MB

 1 class Solution {
 2     func alphabetBoardPath(_ target: String) -> String {
 3         var x:Int = 0
 4         var y:Int = 0
 5         var res:String = String()
 6         let arrTarget:[Int] = Array(target).map{$0.ascii}
 7         for ch in arrTarget
 8         {
 9             var x1:Int = (ch - 97) % 5
10             var y1:Int = (ch - 97) / 5
11             let str:String = String(repeating:"U",count:max(0, y - y1)) + String(repeating:"R",count:max(0, x1 - x)) + String(repeating:"L",count:max(0, x - x1)) + String(repeating:"D",count:max(0, y1 - y)) + "!"       
12             res += str
13             x = x1
14             y = y1
15         }
16         return res
17     }
18 }
19 
20 //Character扩展 
21 extension Character  
22 {  
23   //Character转ASCII整数值(定义小写为整数值)
24    var ascii: Int {
25        get {
26            return Int(self.unicodeScalars.first?.value ?? 0)
27        }       
28     }
29 }

4ms

 1 class Solution {
 2     func alphabetBoardPath(_ target: String) -> String {
 3         let board: [Character: (row: Int, col: Int)] = ["a": (0, 0), "b": (0, 1), "c": (0, 2), "d": (0, 3), "e": (0, 4),
 4                                                     "f": (1, 0), "g": (1, 1), "h": (1, 2), "i": (1, 3), "j": (1, 4),
 5                                                     "k": (2, 0), "l": (2, 1), "m": (2, 2), "n": (2, 3), "o": (2, 4),
 6                                                     "p": (3, 0), "q": (3, 1), "r": (3, 2), "s": (3, 3), "t": (3, 4),
 7                                                     "u": (4, 0), "v": (4, 1), "w": (4, 2), "x": (4, 3), "y": (4, 4),
 8                                                     "z": (5, 0)
 9                                                     ]
10     
11         var prevChar: Character = "a"
12         var moves: String = ""
13     
14         for eachChar in [Character](target) {
15 
16             while eachChar != prevChar {
17                 switch prevChar {
18                     case "z":
19                         moves += "U"
20                         prevChar = "u"
21                         continue
22 
23                     default:
24                         let leftOrRight = board[eachChar]!.col - board[prevChar]!.col
25                         let upOrDown = board[eachChar]!.row - board[prevChar]!.row
26 
27                         switch leftOrRight.signum() { // Move Left or Right
28                             case -1:
29                                 moves += repeatElement("L", count: -leftOrRight)
30                             case 1:
31                                 moves += repeatElement("R", count:  leftOrRight)
32                             default:
33                                 moves.append("")
34                         }
35 
36                         switch upOrDown.signum() { // Then Move Up or Down
37                             case -1:
38                                 moves += repeatElement("U", count: -upOrDown)
39                             case 1:
40                                 moves += repeatElement("D", count:  upOrDown)
41                             default:
42                                 moves.append("")
43                     }
44                 }
45                 prevChar = eachChar
46             }
47             moves += "!"
48         }
49         return moves    
50     }
51 }

8ms

 1 class Solution {
 2     func position(of c: Character) -> (Int, Int) {
 3         let av = Int(c.asciiValue! - 97)
 4         return (av / 5, av % 5)
 5     }
 6     
 7     func path(from a: Character, to b: Character) -> String {
 8         guard a != b else {
 9             return ""
10         }
11         
12         let posA = position(of: a)
13         let posB = position(of: b)
14         
15         if a == "z" {
16             return String(repeating:"U", count:posA.0 - posB.0) + String(repeating:"R", count:posB.1 - posA.1)
17         }
18         if b == "z" {
19             return String(repeating:"L", count: posA.1 - posB.1) + String(repeating:"D", count:posB.0 - posA.0)
20         }
21         
22         return String(repeating:posA.0 > posB.0 ? "U" : "D", count: abs(posA.0 - posB.0)) + String(repeating:posA.1 > posB.1 ? "L" : "R", count: abs(posA.1 - posB.1))
23     }
24     
25     func alphabetBoardPath(_ target: String) -> String {
26         var result = ""
27         var cc : Character = "a"
28         for c in target { 
29            result += path(from: cc, to: c) + "!"
30            cc = c 
31         }
32         return result
33     }
34 }

20ms

 1 class Solution {
 2     let board: [[Character]] = [Array("abcde"), Array("fghij"), Array("klmno"), Array("pqrst"), Array("uvwxy"), Array("z")]
 3     let boardHash: [Character:Position] = 
 4     ["a": Position(0,0), "b": Position(0,1), "c": Position(0,2), "d": Position(0,3), "e": Position(0,4), 
 5      "f": Position(1,0), "g": Position(1,1), "h": Position(1,2), "i": Position(1,3), "j": Position(1,4), 
 6      "k": Position(2,0), "l": Position(2,1), "m": Position(2,2), "n": Position(2,3), "o": Position(2,4), 
 7      "p": Position(3,0), "q": Position(3,1), "r": Position(3,2), "s": Position(3,3), "t": Position(3,4), 
 8      "u": Position(4,0), "v": Position(4,1), "w": Position(4,2), "x": Position(4,3), "y": Position(4,4), 
 9      "z": Position(5,0)]
10     
11     func alphabetBoardPath(_ target: String) -> String {
12         var hash = [Key:[Character]]()
13         return String(_alphabetBoardPath(Array(target), 0, Position(0,0), &hash))
14     }
15     
16     func _alphabetBoardPath(_ target: [Character],
17                             _ i: Int,
18                             _ position: Position,
19                             _ hash: inout [Key:[Character]]) -> [Character] {
20         if i >= target.count { return [] }
21         
22         let targetPosition = boardHash[target[i]]!
23         // let index = Key(i, position, visited)
24         // if let savedSolution = hash[index] { return savedSolution }
25         
26         var solution: [Character] = []
27         if targetPosition == position {
28             solution = ["!"] + _alphabetBoardPath(target, i+1, position, &hash)
29         } else {
30             let downP = Position(position.i+1, position.j)
31             let upP = Position(position.i-1, position.j)
32             let rightP = Position(position.i, position.j+1)
33             let leftP = Position(position.i, position.j-1)
34             
35             if targetPosition.i == position.i {
36                 if position.j < targetPosition.j {
37                     solution = ["R"] + _alphabetBoardPath(target, i, rightP, &hash)
38                 } else {
39                     solution = ["L"] + _alphabetBoardPath(target, i, leftP, &hash)
40                 }
41             } 
42             else {
43                 if position.i < targetPosition.i {
44                     if downP.isValid(for: board) {
45                         solution = ["D"] + _alphabetBoardPath(target, i, downP, &hash)        
46                     } else {
47                         solution = ["L"] + _alphabetBoardPath(target, i, leftP, &hash)
48                     }
49                     
50                 } else {
51                     solution = ["U"] + _alphabetBoardPath(target, i, upP, &hash)
52                 }
53             }
54         }
55         
56         // hash[index] = solution
57         return solution
58     }
59 }
60 
61 struct Key: Hashable {
62     let i: Int
63     let position: Position
64     let visited: Set<Position>
65     
66     init(_ i: Int, _ position: Position, _ visited: Set<Position>) {
67         self.i = i
68         self.position = position
69         self.visited = visited
70     }
71 }
72 
73 struct Position: Hashable {
74     let i: Int
75     let j: Int
76     
77     init(_ i: Int, _ j: Int) {
78         self.i = i
79         self.j = j
80     }
81     
82     func isValid(for board: [[Character]]) -> Bool {
83         return i >= 0 && i < board.count && j >= 0 && j < board[i].count
84     }
85 }