title: 算法小练——最长公共前缀
categories:

  • Algorithms
    tags:
  • esay
    abbrlink: 2222011506
    date: 2019-11-05 19:28:25

最长公共前缀

描述

编写一个函数来查找字符串数组中的最长公共<mark>前缀</mark>。

如果不存在公共前缀，返回空字符串 ""。

示例

####　示例 1:

输入: [“flower”,“flow”,“flight”]
输出: “fl”

示例 2:

输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。

说明

所有输入只包含小写字母 a-z 。

代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
       //思路：把第一个字符串，分词为多个字符串，找到字符串组里其他里是否包含该字符串
        //因为目的是找最长的字符串，所以先找应该从大往小找，这样能够查找次数最少
        if(strs.length ==0){
            return "";
        }
       
        int str0 = strs[0].length(); //最短字符串的长度
        String strShort = strs[0];
        int index = 0;
        for (int i = 1; i < strs.length; i++) {
            if(str0>strs[i].length()){
                str0 = strs[i].length();
                strShort = strs[i];
                index = i;
            }
        }
        char[] chars = strShort.toCharArray();
        for (int i = chars.length; i>0; i--) {
            String s = strShort.substring(0,i);
            boolean flag = true;
            for (int j = 0; j < strs.length; j++) {
                if(j == index){
                    continue;
                }
                String newString = strs[j].substring(0,i);
                if(!newString.contentEquals(s)){
                   flag =false;
                }
            }
            if(flag){
                return s;
            }
        }

        return "";
    }
    
}

笔记

这道题，做的我很心酸，没有仔细读题，最开始当做，从一个字符串组中，找出最长公共子串做了。结果验证的时候出问题了，再仔细读题，才发现是最长前缀。但是就当给自己增加下难度吧，下面会把求最长公共子串的代码，留下。

代码2

// 最长公共子串求解
class Solution {
    public String longestCommonPrefix(String[] strs) {
       //思路：把第一个字符串，分词为多个字符串，找到字符串组里其他里是否包含该字符串
        //因为目的是找最长的字符串，所以先找应该从大往小找，这样能够查找次数最少
        if(strs.length ==0){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }
        int str0 = strs[0].length(); //最短字符串的长度
        String strShort = strs[0];
        int index = 0;
        for (int i = 1; i < strs.length; i++) {
            if(str0>strs[i].length()){
                str0 = strs[i].length();
                strShort = strs[i];
                index = i;
            }
        }
        char[] chars = strShort.toCharArray();
        for (int i = chars.length; i>0; i--) {
            boolean flag = true; //如果有不包含的，则变为false
            String newString= strShort.substring(0,i);
            for (int j = 0; j < strs.length; j++) {
                //如果是该字符串本身，则不比较
                if(j==index){
                    continue;
                }
                if(i==strs[j].length()){
                    if(strs[j].contentEquals(newString)){
                        flag =  true;
                        continue;
                    }
                    flag =false;
                }
                //找一个字符串中是否存在某个字符串
                for (int k = 0; k < strs[j].length()-i; k++) {

                    String stringPart= strs[j].substring(k,k+i);
                    if(stringPart.contentEquals(newString)){
                        flag =  true;
                        break;
                    }
                    flag =false;
                }


            }
            if(flag){
                return newString;
            }
        }

        return "";
    }
}