Swift で LCS：Longest Common Subsequence（最長共通部分列）

備忘用メモ

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