题解 | #最长公共子串#

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * longest common substring
        * @param str1 string字符串 the string
        * @param str2 string字符串 the string
        * @return string字符串
    */
    fun LCS(str1: String,str2: String): String  {
        //使用两个数组交替来储存结果，节省空间
        val dp1 = Array<StringBuilder>(str2.length + 1) { 
                StringBuilder()
            }
        val dp2 = Array<StringBuilder>(str2.length + 1) { 
                StringBuilder()
            }
        var result = ""
        for(i in 1..str1.length) {
            for (j in 1..str2.length) {
                if(str1[i - 1] == str2[j - 1]) dp2[j].append(dp1[j - 1].toString()).append(str1[i - 1])
                if(dp2[j].length > result.length) result = dp2[j].toString()
            }
            swap(dp2, dp1)
        }
        return result
    }
    
    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 substring
        * @param str1 string字符串 the string
        * @param str2 string字符串 the string
        * @return string字符串
    */
    fun LCS(str1: String,str2: String): String  {
        val dp = Array<StringBuilder>(str2.length + 1) { 
                StringBuilder()
            }
        //上面使用两个数组在空间上来说仍然是多余的，因为我们只需要用到前一个数组的相同下标的前一个下标的值即dp1[j - 1]
        //因此我们可以维护两个变量即可，不需要再多一个数组的空间
        var prev = ""
        var temp = ""
        var result = ""
        for(i in 1..str1.length) {
            prev = ""
            for (j in 1..str2.length) {
                temp = dp[j].toString()
                //把上一轮相同下标的值先保存
                dp[j].clear()
                if(str1[i - 1] == str2[j - 1]) dp[j].append(prev).append(str1[i - 1])
                if(dp[j].length > result.length) result = dp[j].toString()
                //把当前的值赋值给prev，到下一轮使用的时候就相当于使用了上一轮的相同下标的前一个值，即dp1[j - 1]
                prev = temp
            }
        }
        return result
    }
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * longest common substring
        * @param str1 string字符串 the string
        * @param str2 string字符串 the string
        * @return string字符串
    */
    fun LCS(str1: String,str2: String): String  {
        val dp = Array<StringBuilder>(str2.length + 1) { 
                StringBuilder()
            }
        var result = ""
        for(i in 1..str1.length) {
            for (j in str2.length downTo 1) {
                dp[j].clear()
                //我们注意到需要用到的值其实只与上一轮相同位置的前一个值有关的话我们逆序遍历的时候就可以直接拿到上一轮的前一个值，因此连临时变量都不用维护
                if(str1[i - 1] == str2[j - 1]) dp[j].append(dp[j - 1]).append(str1[i - 1])
                if(dp[j].length > result.length) result = dp[j].toString()
            }
        }
        return result
    }
}