题解 | #最长公共前缀#

public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
        int len = strs.length;
        if(len == 0){
            return "";
        }
        String str = strs[0];
        for(int i=1;i<len;i++){
            if(str == "" || strs[i] == ""){
                return "";
            }
            str = longestCommonPrefix(str,strs[i]);
        }
        
        return str;
    }
    
    public String longestCommonPrefix(String str1,String str2){
        // write code here
        int length1 = str1.length();
        int length2 = str2.length();
        if(length1 == 0 || length2 == 0){
            return "";
        }
        int[][] dp = new int[length1+1][length2+1];//定义一个dp二维数组
         
        //初始化第一列，表示str1与空字符串的最长公共子串为0
        for(int i = 0;i<length1+1;i++){
            dp[i][0] = 0;
        }
         
        //初始化第一行，表示空字符串与str2的最长公共子串为0
        for(int i = 0;i<length2;i++){
            dp[0][i] = 0;
        }
         
        char[] cha1 = str1.toCharArray();
        char[] cha2 = str2.toCharArray();
        int maxLength = 0;//最长公共子串长度
        int index = 0;//最长公共子串末位在str1的索引
         
        //动态规划，最优子结构，状态转换关系
        //如果(cha1[i] == cha2[j])，dp[i+1][j+1] = dp[i][j] + 1；反之，dp[i+1][j+1] = 0
        //遍历str1，str2，更新dp二维数组
        for(int i = 0;i<length1;i++){
            for(int j = 0;j<length2;j++){
                if(cha1[i] == cha2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                    //更新最长公共子串长度，最长公共子串末位在str1的索引
                    if(maxLength < dp[i+1][j+1]){
                        maxLength = dp[i+1][j+1];
                        index = i;
                    }
                }else{
                    dp[i+1][j+1] = 0;
                }
            }
        }
         
        return str1.substring(index-maxLength+1,index+1);
    }
}