Longest Common Subsequence using Tabulation

longest-common-subsequence-tabulation.swift

func lcs(_ t1: [Character], _ t2: [Character]) -> Int {
    // 1. build and default grid to 0
    let row = Array(repeating: 0, count: t2.count)
    var grid = Array(repeating: row, count: t1.count)
    
    func lcs(_ s: Stage) -> Int {
        // 3. Exit with a 0 for any point that's beyond the left or bottom edges
        guard s.s1 >= 0 && s.s2 >= 0 else {
            return 0
        }
        if t1[s.s1] == t2[s.s2] {
            return (grid.safe(at:s.s1 - 1)?.safe(at:s.s2 - 1) ?? 0) + 1
        } else {
            return max(grid.safe(at:s.s1 - 1)?[s.s2] ?? 0, grid[s.s1].safe(at:s.s2 - 1) ?? 0)
        }
    }
    // 2. starting from top left corner: find the LCS value for every item in the grid. 
    // End at bottom right corner
    
    for row in 0..<grid.count {
        for column in 0..<grid[0].count {
            grid[row][column] = lcs(Stage(row,column))
        }
    }

    // return the last result at the end of your tabulation
    return grid[t1.count - 1][t2.count - 1] 
}


extension Array {
    func safe(at index: Int) -> Element? {
        guard index < count && index >= 0 else { 
            return nil
        }
        return self[index]
    }
}

struct Stage: Hashable {
    var s1: Int
    var s2: Int
    
    init(_ s1: Int, _ s2: Int) {
        self.s1 = s1
        self.s2 = s2
    }
}