備忘用メモ

NOTE

問題：https://leetcode.com/problems/longest-common-subsequence
実装：DP
計算量：O(MN)（長さMと長さNの文字列）

コード

func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
    let len1 = text1.count
    let len2 = text2.count
    var dp = [[Int]](repeating: [Int](repeating: 0, count: len2+1), count: len1+1)
    let list1 = Array(text1)
    let list2 = Array(text2)
    
    for i in 1..<len1+1 {
        for j in 1..<len2+1 {
            let strI = i - 1
            let strJ = j - 1
            if list1[strI] == list2[strJ] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            }
        }
    }
    return dp[len1][len2]
}

ポイント

i/jのインデックスが文字とdpでズレてる
- 個人的には、混乱するので明示的に strI / strJ で定義しちゃうほうがわかりやすい
２ケースについて考える：
- 青色：S[strI] == S[strJ]の場合、dp[i-1][j-1]+1
- 赤色：S[strI] != S[strJ]の場合、max(dp[i-1][j], dp[i][j-1])

REF

http://www.cs.t-kougei.ac.jp/SSys/LCS.htm