题解 | 最长公共子串

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