Longest Common Subsequence Algorithm

[iWeslie]

Brief Intro

Longest Common Subsequence Algorithm wiki link

e.g.: "ABCDBAB" and "BDCABA"

LCS -> "BCBA"

Dynamic Programming:

c[i,j] stored the length of longest subsequence

Subsequence can be not continuous, but substring must be continuous.

More Details

algorithm detail (using Dynamic Programming):

func lcs(_ str1: String, _ str2: String) -> String {
    var arr1 = Array(str1)
    var arr2 = Array(str2)
    arr1.insert("$", at: 0) // char notation as a placeholder
    arr2.insert("$", at: 0) // count from 1 to n, easy to impelment
    let n = arr1.count
    let m = arr2.count

    var chess = Array(repeating: Array(repeating: 0, count: m), count: n)

    for i in 1..<n {
        for j in 1..<m {
            if arr1[i] == arr2[j] {
                chess[i][j] = chess[i-1][j-1] + 1
            } else {
                chess[i][j] = max(chess[i][j-1], chess[i-1][j])
            }
        }
    }

    var i = n - 1
    var j = m - 1

    var result = ""
    while i > 0 && j > 0 { 
        if arr1[i] == arr2[j] {
            result.append(arr1[i]) // check the top left matched
            i -= 1
            j -= 1
        } else {
            if chess[i][j-1] > chess[i-1][j] {
                j -= 1
            } else {
                i -= 1
            }
        }
    }

    return String(result.reversed())
}

test:

let stringA = "ABCDBAB"
let stringB = "BDCABA"
lcs(stringA, stringB)

return: "BCBA"

[kelvinlauKL]

Thanks for the suggestion! If you're interested in writing a tutorial about this, feel free to make a pull request and follow our style guidelines