문자열의 편집거리 구하기

main.swift

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"))