8000 Add solutions · zenglekidd/LeetcodeInSwift@a0004e3 · GitHub
[go: up one dir, main page]
Skip to content

Commit a0004e3

Browse files
zenglekiddzenglekidd
committed
Add solutions
1 parent 06e46ff commit a0004e3

File tree

5 files changed

+130
-0
lines changed

5 files changed

+130
-0
lines changed

‎127. Word Ladder.playground/Contents.swift

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
import Foundation
2+
3+
/*
4+
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
5+
6+
Only one letter can be changed at a time.
7+
Each transformed word must exist in the word list.
8+
Note:
9+
10+
Return 0 if there is no such transformation sequence.
11+
All words have the same length.
12+
All words contain only lowercase alphabetic characters.
13+
You may assume no duplicates in the word list.
14+
You may assume beginWord and endWord are non-empty and are not the same.
15+
16+
Example 1:
17+
Input:
18+
beginWord = "hit",
19+
endWord = "cog",
20+
wordList = ["hot","dot","dog","lot","log","cog"]
21+
22+
Output: 5
23+
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
24+
return its length 5.
25+
26+
Example 2:
27+
Input:
28+
beginWord = "hit"
29+
endWord = "cog"
30+
wordList = ["hot","dot","dog","lot","log"]
31+
32+
Output: 0
33+
34+
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
35+
*/
36+
37+
class Solution {
38+
func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
39+
var wordSet: Set<String> = Set(wordList)
40+
if wordSet.contains(endWord) == false {return 0}
41+
42+
var result = 1
43+
44+
var todo: [String] = [beginWord]
45+
46+
while todo.isEmpty == false {
47+
let n = todo.count
48+
for _ in 0 ..< n {
49+
let word = todo.removeFirst()
50+
if word == endWord {
51+
return result
52+
}
53+
54+
for j in 0 ..< word.count {
55+
var wordArray = Array(word)
56+
let c = wordArray[j]
57+
for k in Array("abcdefghijklmnopqrstuvwxyz") {
58+
wordArray[j] = k
59+
if wordSet.contains(String(wordArray)) {
60+
todo.append(String(wordArray))
61+
wordSet.remove(String(wordArray))
62+
}
63+
}
64+
wordArray[j] = c
65+
}
66+
}
67+
result += 1
68+
}
69+
70+
return 0
71+
}
72+
}
73+
74+
import Foundation
75+
import XCTest
76+
class SolutionTests: XCTestCase {
77+
var solution: Solution!
78+
override func setUp() {
79+
super.setUp()
80+
solution = Solution()
81+
}
82+
83+
func test1() {
84+
let beginWord = "hit"
85+
let endWord = "cog"
86+
let wordList = ["hot","dot","dog","lot","log","cog"]
87+
let results = solution.ladderLength(beginWord, endWord, wordList)
88+
XCTAssertEqual(results, 5)
89+
}
90+
91+
func test2() {
92+
let beginWord = "hit"
93+
let endWord = "cog"
94+
let wordList = ["hot","dot","dog","lot","log"]
95+
let results = solution.ladderLength(beginWord, endWord, wordList)
96+
XCTAssertEqual(results, 0)
97+
}
98+
}
99+
100+
SolutionTests.defaultTestSuite.run()

‎127. Word Ladder.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>

‎127. Word Ladder.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.

‎127. Word Ladder.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>

‎127. Word Ladder.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/Documents/github/LeetcodeInSwift/127.%20Word%20Ladder.playground#CharacterRangeLen=1170&amp;CharacterRangeLoc=1000&amp;EndingColumnNumber=1&amp;EndingLineNumber=71&amp;StartingColumnNumber=0&amp;StartingLineNumber=36&amp;Timestamp=624819772.086244"
7+
selectedRepresentationIndex = "0"
8+
shouldTrackSuperviewWidth = "NO">
9+
</LoggerValueHistoryTimelineItem>
10+
</TimelineItems>
11+
</Timeline>

0 commit comments

Comments
 (0)
0