题解 | #最长公共子串# #C##

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public string LCS (string str1, string str2) {
        int[] dp = new int [str2.Length + 1];
        int ansStart = -1, ansCount = 0;
        for(int i = 1; i <= str1.Length; i++){
            for(int j = str2.Length; j >= 1; j--){
                if(str1[i - 1] == str2[j - 1]){
                    dp[j] = dp[j - 1] + 1;
                    if(dp[j] > ansCount){
                        ansCount = dp[j];
                        ansStart = j - ansCount;
                    }
                }
                else dp[j] = 0;
            }
        }
        return ansCount > 0 ? str2.Substring(ansStart, ansCount) : "";
    }
}