题解 | #最长公共子序列(二)#

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * longest common subsequence
        * @param s1 string字符串 the string
        * @param s2 string字符串 the string
        * @return string字符串
    */
    fun LCS(s1: String,s2: String): String  {
        val dp = Array<Array<StringBuilder>>(s1.length + 1) {
            Array<StringBuilder>(s2.length + 1) {
                StringBuilder()
            }
        }
        for(i in 1..s1.length) {
            for(j in 1..s2.length) {
                if(s1[i - 1] == s2[j - 1]) {
                    dp[i][j].append(dp[i - 1][j - 1].toString()).append(s2[j - 1])
                }
                else  {
                    if (dp[i - 1][j].length > dp[i][j - 1].length) dp[i][j].append(dp[i - 1][j].toString())  else dp[i][j].append(dp[i][j - 1].toString())
                }
            }
        }
        if(dp[s1.length][s2.length].length == 0) return "-1"
        return dp[s1.length][s2.length].toString()
    }
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * longest common subsequence
        * @param s1 string字符串 the string
        * @param s2 string字符串 the string
        * @return string字符串
    */
    fun LCS(s1: String,s2: String): String  {
        //注意到其实我们的状态转移只与前一个数组有关（dp[i - 1][j - 1] 其中i - 1 表示使用前一个数组记录的值），因为我们维护两个数组，然后内部循环完之后交换数组的值就行了，这样可以节省空间
        val dp1 = Array<StringBuilder>(s2.length + 1) {
                StringBuilder()
            }
        val dp2 = Array<StringBuilder>(s2.length + 1) {
                StringBuilder()
            }
        for(i in 1..s1.length) {
            for(j in 1..s2.length) {
                if(s1[i - 1] == s2[j - 1]) {
                    dp2[j].append(dp1[j - 1].toString()).append(s2[j - 1])
                }
                else  {
                    if (dp1[j].length > dp2[j - 1].length) dp2[j].append(dp1[j].toString())  else dp2[j].append(dp2[j - 1].toString())
                }
            }
            //交换数组的值
            swap(dp2, dp1)
        }
        if(dp1[s2.length].length == 0) return "-1"
        return dp1[s2.length].toString()
    }
    
    private inline fun swap(src: Array<StringBuilder>, des: Array<StringBuilder>) {
        for(i in src.indices) {
            //清楚之前的数据然后添加新数据
            des[i].clear()
            des[i].append(src[i].toString())
            //清楚数据，等一下会添加新的数据
            src[i].clear()
        }
    }
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * longest common subsequence
        * @param s1 string字符串 the string
        * @param s2 string字符串 the string
        * @return string字符串
    */
    fun LCS(s1: String,s2: String): String  {
        val dp = Array<StringBuilder>(s2.length + 1) {
                StringBuilder()
            }
        /之前使用滚动数组来减少空间，但实际上这任然是浪费空间的，我们注意到我们实际上只使用了上一个数组的相同下标或前一个下标的值(dp[i - 1][j - 1] 表示前一个数组的当前下标的前一个值，dp[i - 1][j] 表示前一个数组相同下标的值)
        //因此我们可以用两个变量来记住这两个值即可
        var prev = ""
        var temp = ""
        for(i in 1..s1.length) {
            //开始前为初始状态
            prev = ""
            for(j in 1..s2.length) {
                //此时temp相当于dp[i - 1][j]
                temp = dp[j].toString()
                dp[j].clear()
                if(s1[i - 1] == s2[j - 1]) {
                    dp[j].append(prev).append(s2[j - 1])
                }
                else  {
                    if (temp.length > dp[j - 1].length) dp[j].append(temp)  else dp[j].append(dp[j - 1].toString())
                }
                //此时赋值给prev下一轮使用的时候相当于dp[i - 1][j - 1]
                prev = temp
            }
        }
        if(dp[s2.length].length == 0) return "-1"
        return dp[s2.length].toString()
    }
}