题解 | #最长公共前缀#

最长公共前缀

http://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47



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);
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:20
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务