Skip to content

Commit 6063538

Browse files
soapyigusoapyigu
committed
[DFS] Add a solution to Word Squares
1 parent 0f49a09 commit 6063538

File tree

4 files changed

+68
-5
lines changed

4 files changed

+68
-5
lines changed

‎DFS/NQueens.swift

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
* Primary idea: Classic Depth-first Search, fill out row by row, and check column and
44
* diagnol for each time
55
*
6-
* Time Complexity: O(n^4), Space Complexity: O(n^2)
6+
* Time Complexity: O(n!), Space Complexity: O(n^2)
77
*
88
*/
99

‎DFS/NQueensII.swift

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
* Primary idea: Classic Depth-first Search, fill out row by row, and check column and
44
* diagnol for each time, only need to care which column is used
55
*
6-
* Time Complexity: O(n^3), Space Complexity: O(n)
6+
* Time Complexity: O(n!), Space Complexity: O(n)
77
*
88
*/
99

‎DFS/WordSquares.swift

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/word-squares/
3+
* Primary idea: Classic Depth-first Search, fill out row by row, choose correct word with fixed prefix, only need to care which column is used
4+
*
5+
* Time Complexity: O(n!), Space Complexity: O(n)
6+
*
7+
*/
8+
9+
class WordSquares {
10+
func wordSquares(_ words: [String]) -> [[String]] {
11+
var paths = [[String]]()
12+
13+
guard words.count > 0 else {
14+
return paths
15+
}
16+
17+
var prefixWords = initPrefix(words), path = [String]()
18+
19+
dfs(&paths, &path, prefixWords, 0, words[0].count)
20+
21+
return paths
22+
}
23+
24+
fileprivate func dfs(_ paths: inout [[String]], _ path: inout [String], _ prefixWords: [String:[String]], _ row: Int, _ len: Int) {
25+
if row == len {
26+
paths.append(Array(path))
27+
return
28+
}
29+
30+
var pre = ""
31+
for i in 0..<row {
32+
pre = "\(pre)\(Array(path[i])[row])"
33+
}
34+
35+
guard let words = prefixWords[pre] else {
36+
return
37+
}
38+
39+
for word in words {
40+
path.append(word)
41+
dfs(&paths, &path, prefixWords, row + 1, len)
42+
path.removeLast()
43+
}
44+
}
45+
46+
fileprivate func initPrefix(_ words: [String]) -> [String: [String]]{
47+
var prefix = [String: [String]]()
48+
49+
for word in words {
50+
prefix[""] = prefix["", default:[]] + [word]
51+
52+
var pre = ""
53+
for c in word {
54+
pre = "\(pre)\(c)"
55+
56+
prefix[pre] = prefix[pre, default:[]] + [word]
57+
}
58+
}
59+
60+
return prefix
61+
}
62+
}

‎README.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
* [Microsoft](#microsoft)
2929

3030
## Progress
31-
[Problem Status](#problem-status) shows the latest progress to all 800+ questions. Currently we have 250 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them. Thank you for great contributions from [CharleneJiang](https://github.com/CharleneJiang), [ReadmeCritic](https://github.com/ReadmeCritic), [demonkoo](https://github.com/demonkoo), [DaiYue](https://github.com/DaiYue), [Quaggie](https://github.com/Quaggie) and [jindulys](https://github.com/jindulys).
31+
[Problem Status](#problem-status) shows the latest progress to all 800+ questions. Currently we have 251 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them. Thank you for great contributions from [CharleneJiang](https://github.com/CharleneJiang), [ReadmeCritic](https://github.com/ReadmeCritic), [demonkoo](https://github.com/demonkoo), [DaiYue](https://github.com/DaiYue), [Quaggie](https://github.com/Quaggie) and [jindulys](https://github.com/jindulys).
3232

3333

3434
## Array
@@ -233,8 +233,9 @@
233233
[Word Search](https://leetcode.com/problems/word-search/)| [Swift](./DFS/WordSearch.swift)| Medium| O((n^2)!)| O(n^2)|
234234
[Word Search II](https://leetcode.com/problems/word-search-ii/)| [Swift](./DFS/WordSearchII.swift)| Hard| O(((mn)^2))| O(n^2)|
235235
[Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/)| [Swift](./DFS/WordDictionary.swift)| Medium| O(n)| O(n)|
236-
[N-Queens](https://leetcode.com/problems/n-queens/)| [Swift](./DFS/NQueens.swift)| Hard| O((n^4))| O(n^2)|
237-
[N-Queens II](https://leetcode.com/problems/n-queens-ii/)| [Swift](./DFS/NQueensII.swift)| Hard| O((n^3))| O(n)|
236+
[N-Queens](https://leetcode.com/problems/n-queens/)| [Swift](./DFS/NQueens.swift)| Hard| O((n!))| O(n^2)|
237+
[N-Queens II](https://leetcode.com/problems/n-queens-ii/)| [Swift](./DFS/NQueensII.swift)| Hard| O((n!))| O(n)|
238+
[Word Squares](https://leetcode.com/problems/word-squares/)| [Swift](./DFS/WordSquares.swift)| Hard| O((n!))| O(n)|
238239
[Sudoku Solver](https://leetcode.com/problems/sudoku-solver/)| [Swift](./DFS/SudokuSolver.swift)| Hard| O(n^4)| O(1)|
239240
[Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)| [Swift](./DFS/RemoveInvalidParentheses.swift)| Hard| O(n!)| O(n)|
240241
[Expression Add Operators](https://leetcode.com/problems/expression-add-operators/)| [Swift](./DFS/ExpressionAddOperators.swift)| Hard| O(n!)| O(n)|

0 commit comments

Comments
 (0)