• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap