【leetcode】【初级算法】【字符串9】最长公共前缀

题目

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

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

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

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

题解一：横向扫描

自己写的，是官方题解的方法一，前两个字符串先比较出最长公共前缀，再把公共前缀跟下一个比较。

java解

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length ==0){
            return "";
        }
        // java中字符串的长度和数组的长度函数不同；
        int length = strs.length;
        String str1 = new String();
        String str2 = new String();
        str1 = strs[0];
        for(int i = 0;i<length-1;i++){
            StringBuilder sb = new StringBuilder();
            str2 = strs[i+1];
            int slength =0;
            if (str1.length()>str2.length()){
                slength = str2.length();                
            }
            else{
                slength = str1.length();
            }
            int pos = 0;
            while(pos<slength){
                if(str1.charAt(pos)==str2.charAt(pos)){
                    pos++;
                }else{
                    break;
                }
            }
            if(pos==0){
                return "";
            }
            for(int j=0;j<pos;j++){
                sb.append(str2.charAt(j));                
            }
            str1 = sb.toString();
        }
        return str1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

官方题解中因为每次和公共前缀的比较 操作相同所以，将比价写为函数。
substring()
（1）substring是用来截取字符串的，根据参数的个数不同，方法含义也不同；
（2）substring(0,2)这个只含开头不含结尾，因此截取是截取两个字符，从第一个到第二个字符，不包含第三个。
（3）substring(2)这个表示截掉前两个，得到后边的新字符串。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组是空，或者长度为零，则最长公共前缀就返回""
        if(strs==null || strs.length==0){
            return "";
        }
        // 定义一个存放公共前缀的字符串
        String prefix = strs[0];
        // 定义一个存放字符串数组长度的变量 count
        int count = strs.length;
        // 遍历字符串数组中每一个字符串
        for(int i=1;i<count;i++){
            prefix = longestCommonPrefix(prefix,strs[i]);
            if(prefix.length()==0){
                break;
            }
        }
        return prefix;
        
    }
    // 比较两个字符串的最长公共前缀
    public String longestCommonPrefix(String str1,String str2){
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while(index<length && str1.charAt(index)==str2.charAt(index)){
            index++;
        }
        return str1.substring(0,index);
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

python解

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 方法一 横向扫描
        # 第一步 判空
        if not strs:
            return ""
        # 第二步 定义参数 存放公共前缀 存放数组长度
        prefix = strs[0]
        count = len(strs)
        # 第三步 遍历比价得到最长公共前缀
        for i in range(1,count):
            prefix = self.lcp(prefix,strs[i])
            # 返回的就是最长公共前缀了，再判断一下是否为空
            if not prefix:
                break
        return prefix
    
    def lcp(self, str1, str2):
        # 第一步 遍历前准备，只用遍历最短的字符就好 再定义一个索引
        length = min(len(str1),len(str2))
        index = 0
        # 遍历
        while index<length and str1[index]==str2[index]:
            index+=1
        return str1[:index]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

题解二：纵向扫描

java解

遍历每个字符串的第一个元素是否都相等（j），再循环第二个元素。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 第一步先判空 学习数组的判空方式
        if(strs==null || strs.length == 0){
            return "";
        }
        // 第二步定义需要的变量 存放第一个字符串的长度length
        int length = strs[0].length();
        // 定义存放字符串数组的长度变量 count
        int count = strs.length;
        // 遍历
        for(int i = 0 ;i<length;i++){
            // 当前比较第i个字符
            char c = strs[0].charAt(i);
            for(int j=1;j<count;j++){
                if(i==strs[j].length() || strs[j].charAt(i) != c){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

python解

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 方法二 纵向扫描
        # 第一步：判空
        if not strs:
            return ""
        # 第二步：遍历前准备工作，定义参数
        length = len(strs[0])
        count = len(strs)
        # 第三步：遍历
        for i in range(length):
            c = strs[0][i]
  #          if any(i==len(strs[j]) or strs[j][i]!=c for j in range(1,count)):
            for j in range(1,count):
                if i==len(strs[j]) or c!=strs[j][i]:
                    return strs[0][:i]
        return strs[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题解三：分治

Java解

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 判空
        if(strs == null || strs.length == 0){
            return "";
        }
        else{
            // 不是空的就返回最长公共前缀
            return longestCommonPrefix(strs,0,strs.length-1);            
        }
    
    }
    
    // 分治分治左右两半 函数的参数是字符串以及 字符串的开头和结尾指针
    public String longestCommonPrefix(String[] strs, int start, int end){
        // 结束条件
        if(start == end){
            return strs[start];
        }else{
            // 左右两边做同样操作
            int mid = (end-start)/2+start;
            String lcpLeft = longestCommonPrefix(strs,start,mid);
            String lcpRight = longestCommonPrefix(strs,mid+1,end);
            // 返回左右两边的公共前缀
            return commonPrefix(lcpLeft,lcpRight);
            
            }
    }
    
    // 这是一个返回左和右字符串公共前缀的函数，参数是左字符串和右字符串
    public String commonPrefix(String lcpLeft,String lcpRight){
        //只用判断较短的长度
        int minLength = Math.min(lcpLeft.length(),lcpRight.length());
        // 如果当前位置i的字符不想等 返回当前的最长公共前缀
        for(int i=0;i<minLength;i++){
            if(lcpLeft.charAt(i)!= lcpRight.charAt(i)){
                return lcpLeft.substring(0,i);
            }
        }
        // 循环完之后发现没有不想等的 就返回最短的这个字符串。
        return lcpLeft.substring(0,minLength);
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

python解

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 方法三 分治
        # 第一步 定义一个函数处理从字符串开始statt到结尾end的函数
        def lcp(start, end):
            # 终止条件：处理start指针到end指针处理完为止
            if start == end:
                return strs[start]
            
            # 分治的思想就是不断的从中间分开 分成小问题处理
            mid = (start+end)//2
            lcpleft,lcpRight = lcp(start,mid),lcp(mid+1,end)
            # 只用比较较短的字符串长度就可
            minLength = min(len(lcpLeft),len(lcpRight))
            # 遍历 一旦不想等就返回当前长度即为最长公共前缀。
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    return lcpLeft[:i]
                
            return lcpLeft[:minLength]
        return "" if not strs else lcp(0,len(strs)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21