8000 Added Day 89 solutions · zenglekidd/LeetcodeInSwift@adc6135 · GitHub
[go: up one dir, main page]
Skip to content

Commit adc6135

Browse files
zenglekiddzenglekidd
committed
Added Day 89 solutions
1 parent 0dbd3c0 commit adc6135

File tree

8 files changed

+288
-0
lines changed

8 files changed

+288
-0
lines changed

‎130. Surrounded Regions.playground/Contents.swift

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
import UIKit
2+
3+
/*
4+
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
5+
6+
A region is captured by flipping all 'O's into 'X's in that surrounded region.
7+
8+
Example:
9+
10+
X X X X
11+
X O O X
12+
X X O X
13+
X O X X
14+
After running your function, the board should be:
15+
16+
X X X X
17+
X X X X
18+
X X X X
19+
X O X X
20+
Explanation:
21+
22+
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
23+
*/
24+
25+
class Solution {
26+
var shouldKeepEverything = false
27+
28+
func solve(_ board: inout [[Character]]) {
29+
if board.count == 0 { return }
30+
let row = board.count
31+
let column = board[0].count
32+
33+
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
34+
35+
for m in 0 ..< row {
36+
for n in 0 ..< column {
37+
if board[m][n] == "O" && visited[m][n] == false {
38+
var current = board
39+
dfs(&current, m, n, &visited)
40+
if shouldKeepEverything == false {
41+
// reset board
42+
board = current
43+
} else {
44+
// reset flag
45+
shouldKeepEverything = false
46+
}
47+
48+
}
49+
}
50+
}
51+
}
52+
53+
func dfs(_ board: inout [[Character]], _ m: Int, _ n: Int, _ visited: inout [[Bool]]) {
54+
if board.count == 0 {return}
55+
let row = board.count
56+
let column = board[0].count
57+
58+
visited[m][n] = true
59+
board[m][n] = "X"
60+
if m == 0 || n == 0 || m == row - 1 || n == column - 1 {
61+
// keep everything
62+
shouldKeepEverything = true
63+
}
64+
65+
let diff = [
66+
(1,0),
67+
(-1,0),
68+
(0,-1),
69+
(0,1),
70+
]
71+
for (x, y) in diff {
72+
if isSafe(&board, m + x, n + y, &visited) {
73+
dfs(&board, m + x, n + y, &visited)
74+
}
75+
}
76+
}
77+
78+
func isSafe(_ board: inout [[Character]], _ m: Int, _ n: Int, _ visited: inout [[Bool]]) -> Bool {
79+
let row = board.count
80+
let column = board[0].count
81+
if m >= 0 && m <= row - 1 && n >= 0 && n <= column - 1 && board[m][n] == "O" && visited[m][n] == false {
82+
return true
83+
}
84+
return false
85+
}
86+
}
87+
88+
import Foundation
89+
import XCTest
90+
class SolutionTests: XCTestCase {
91+
var solution: Solution!
92+
override func setUp() {
93+
super.setUp()
94+
solution = Solution()
95+
}
96+
97+
func test1() {
98+
var input: [[Character]] = [
99+
["X","X","X","X"],
100+
["X","O","O","X"],
101+
["X","X","O","X"],
102+
["X","O","X","X"],
103+
]
104+
105+
let result: [[Character]] = [
106+
["X","X","X","X"],
107+
["X","X","X","X"],
108+
["X","X","X","X"],
109+
["X","O","X","X"],
110+
]
111+
112+
solution.solve(&input)
113+
XCTAssertEqual(input, result)
114+
}
115+
}
116+
117+
SolutionTests.defaultTestSuite.run()

‎130. Surrounded Regions.playground/contents.xcplayground

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
2+
<playground version='5.0' target-platform='ios'>
3+
<timeline fileName='timeline.xctimeline'/>
4+
</playground>

‎130. Surrounded Regions.playground/playground.xcworkspace/contents.xcworkspacedata

Lines changed: 7 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎130. Surrounded Regions.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
3+
<plist version="1.0">
4+
<dict>
5+
<key>IDEDidComputeMac32BitWarning</key>
6+
<true/>
7+
</dict>
8+
</plist>

‎130. Surrounded Regions.playground/timeline.xctimeline

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<Timeline
3+
version = "3.0">
4+
<TimelineItems>
5+
<LoggerValueHistoryTimelineItem
6+
documentLocation = "file:///Users/zenglekidd/Desktop/130.%20Surrounded%20Regions.playground#CharacterRangeLen=1888&amp;CharacterRangeLoc=728&amp;EndingColumnNumber=5&amp;EndingLineNumber=84&amp;StartingColumnNumber=0&amp;StartingLineNumber=27&amp;Timestamp=623939315.444613"
7+
selectedRepresentationIndex = "0"
8+
shouldTrackSuperviewWidth = "NO">
9+
</LoggerValueHistoryTimelineItem>
10+
</TimelineItems>
11+
</Timeline>

‎44. Wildcard Matching.playground/Contents.swift

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
import UIKit
2+
3+
/*
4+
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
5+
6+
'?' Matches any single character.
7+
'*' Matches any sequence of characters (including the empty sequence).
8+
The matching should cover the entire input string (not partial).
9+
10+
Note:
11+
12+
s could be empty and contains only lowercase letters a-z.
13+
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
14+
Example 1:
15+
16+
Input:
17+
s = "aa"
18+
p = "a"
19+
Output: false
20+
Explanation: "a" does not match the entire string "aa".
21+
Example 2:
22+
23+
Input:
24+
s = "aa"
25+
p = "*"
26+
Output 93C6 : true
27+
Explanation: '*' matches any sequence.
28+
Example 3:
29+
30+
Input:
31+
s = "cb"
32+
p = "?a"
33+
Output: false
34+
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
35+
Example 4:
36+
37+
Input:
38+
s = "adceb"
39+
p = "*a*b"
40+
Output: true
41+
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
42+
Example 5:
43+
44+
Input:
45+
s = "acdcb"
46+
p = "a*c?b"
47+
Output: false
48+
*/
49+
50+
class Solution {
51+
func isMatch(_ s: String, _ p: String) -> Bool {
52+
var i = 0
53+
var j = 0
54+
var match = 0
55+
var star = -1
56+
57+
let sArray = Array(s)
58+
let pArray = Array(p)
59+
60+
while i < sArray.count {
61+
if j < pArray.count && (sArray[i] == pArray[j] || pArray[j] == "?") {
62+
i += 1
63+
j += 1
64+
} else if j < pArray.count && (pArray[j] == "*") {
65+
star = j
66+
match = i
67+
j += 1
68+
} else if star != -1 {
69+
j = star + 1
70+
match += 1
71+
i = match
72+
} else {
73+
return false
74+
}
75+
}
76+
77+
while j < pArray.count && pArray[j] == "*" {
78+
j += 1
79+
}
80+
81+
return j == pArray.count
82+
}
< 10000 /td>
83+
}
84+
85+
import Foundation
86+
import XCTest
87+
class SolutionTests: XCTestCase {
88+
var solution: Solution!
89+
override func setUp() {
90+
super.setUp()
91+
solution = Solution()
92+
}
93+
94+
func test1() {
95+
let s = "aa"
96+
let p = "a"
97+
let results = solution.isMatch(s, p)
98+
XCTAssertEqual(results, false)
99+
}
100+
101+
func test2() {
102+
let s = "aa"
103+
let p = "*"
104+
let results = solution.isMatch(s, p)
105+
XCTAssertEqual(results, true)
106+
}
107+
108+
func test3() {
109+
let s = "cb"
110+
let p = "?a"
111+
let results = solution.isMatch(s, p)
112+
XCTAssertEqual(results, false)
113+
}
114+
115+
func test4() {
116+
let s = "adceb"
117+
let p = "*a*b"
118+
let results = solution.isMatch(s, p)
119+
XCTAssertEqual(results, true)
120+
}
121+
122+
func test5() {
123+
let s = "acdcb"
124+
let p = "a*c?b"
125+
let results = solution.isMatch(s, p)
126+
XCTAssertEqual(results, false)
127+
}
128+
}
129+
130+
SolutionTests.defaultTestSuite.run()

‎44. Wildcard Matching.playground/contents.xcplayground

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
2+
<playground version='5.0' target-platform='ios' buildActiveScheme='true'>
3+
<timeline fileName='timeline.xctimeline'/>
4+
</playground>

‎44. Wildcard Matching.playground/playground.xcworkspace/contents.xcworkspacedata

Lines changed: 7 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)
0