Skip to content

Instantly share code, notes, and snippets.

@sooop
Last active Jan 30, 2018
Embed
What would you like to do?
문자열의 편집거리 구하기
private extension String {
subscript(i:Int) -> Character {
let idx = index(startIndex, offsetBy: i)
return self[idx]
}
}
struct Array2D<T> {
let width: Int, height: Int
var length: Int { return width * height }
var data: [T?]
var last: T? { return data.last! }
init(width:Int, height: Int) {
self.width = width
self.height = height
data = Array<T?>(repeating:nil, count: width * height)
}
subscript(row: Int, col: Int) -> T? {
get {
guard case (0..<length) = row * col,
case (0..<width) = col,
case (0..<height) = row
else { return nil }
return data[row*width + col]
}
set {
guard case (0..<length) = row * col,
case (0..<width) = col,
case (0..<height) = row
else { return }
data[row*width + col] = newValue
}
}
subscript(i:Int) -> T? {
get { return data[i] }
set { data[i] = newValue }
}
}
public extension String {
func editDistance(to s: String) -> Int {
var grid = Array2D<Int>(width: s.count+1, height: count+1)
(0...count).forEach{ grid[$0, 0] = $0 }
(0...s.count).forEach{ grid[0, $0] = $0 }
for i in 1...count {
for j in 1...s.count {
if let x = grid[i, j-1],
let y = grid[i-1, j],
let z = grid[i-1, j-1]
{
grid[i, j] = Swift.min(x+1, y+1, z + (self[i-1] == s[j-1] ? 0 : 1))
}
}
}
return grid.last!
}
}
let s = "hello"
print(s.editDistance(to:"helloworld"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment