【经典算法】LeetCode14:最长公共前缀(Java/C/Python3实现含注释说明，Easy)

• 标签：字符串处理、前缀判断

题目

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

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

示例 1：

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

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

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

原题：LeetCode 14

思路及实现

方式一：横向扫描

思路

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，则返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 将第一个字符串作为前缀进行初始化
        String prefix = strs[0];

        // 数组中字符串的数量
        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
32
33
34
35
36
37
38
39
40
41
42
43
44
45

说明：
首先，通过判断字符串数组strs是否为空或长度为0，来确定是否存在最长公共前缀。如果数组为空或长度为0，则直接返回空字符串。
将字符串数组中的第一个字符串作为初始化的最长公共前缀prefix。
使用一个循环遍历剩余的字符串，依次计算最长公共前缀。在每次循环中，调用longestCommonPrefix()方法，将当前最长公共前缀prefix和当前遍历的字符串进行比较，更新最长公共前缀。
如果最长公共前缀为空字符串，则说明不存在公共前缀，无需继续循环，直接跳出。 最后，返回最长公共前缀prefix。
longestCommonPrefix()方法是一个内部方法，用于找到两个字符串str1和str2的最长公共前缀。
首先，获取两个字符串的最小长度length。 初始化索引index为0。
遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。
最后，返回前缀部分的字符串，即str1中的前index个字符。

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或者长度为0，则返回空字符串
    if (strs == NULL || strsSize == 0)
        return "";

    // 将第一个字符串作为初始的最长公共前缀
    char* prefix = strs[0];

    // 遍历数组剩余的字符串，更新最长公共前缀
    for (int i = 1; i < strsSize; i++) {
        prefix = lcp(prefix, strs[i]);
        
        // 如果最长公共前缀为空，则跳出循环
        if (prefix[0] == '\0')
            break;
    }
    
    return prefix;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

说明：
longestCommonPrefix() 函数用于找到字符串数组 strs 中的最长公共前缀。
首先，判断字符串数组是否为空或长度为0，如果是，则直接返回空字符串。 将数组的第一个字符串作为初始的最长公共前缀 prefix。
遍历数组剩余的字符串，调用 lcp() 函数计算当前字符串与当前最长公共前缀的公共前缀，并更新最长公共前缀 prefix。
如果最长公共前缀为空字符串，则无需继续遍历，跳出循环。 返回最长公共前缀 prefix。 lcp() 函数用于找到两个字符串 str1 和str2 的最长公共前缀。 获取两个字符串的最小长度 length。 初始化索引 index 为0。
遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。 创建一个新的字符串来存储最长公共前缀commonPrefix。
使用 strncpy() 函数从 str1 复制 index 个字符到 commonPrefix 中。 在
commonPrefix 的末尾添加字符串结束符 ‘\0’。 返回最长公共前缀 commonPrefix。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 如果字符串数组为空，则返回空字符串
        if not strs:
            return ""
        
        # 将数组的第一个字符串作为初始的最长公共前缀
        prefix, count = strs[0], 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, index = min(len(str1), len(str2)), 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
26
27
28
29
30
31

说明：
longestCommonPrefix()方法是一个类方法，用于找到字符串数组strs中的最长公共前缀。
首先，判断字符串数组是否为空，如果为空，则直接返回空字符串。 将数组的第一个字符串作为初始的最长公共前缀 prefix。
获取数组中的字符串数量 count。 使用一个循环遍历剩余的字符串，调用 lcp()
方法来计算当前字符串与当前最长公共前缀的公共前缀，并更新最长公共前缀 prefix。 如果最长公共前缀为空字符串，则无需继续遍历，跳出循环。
返回最长公共前缀 prefix。 lcp() 方法是一个类方法，用于找到两个字符串 str1 和 str2 的最长公共前缀。
获取两个字符串的最小长度 length。 初始化索引 index 为0。
遍历两个字符串，比较对应位置的字符是否相等，直到遇到不相等的字符或到达较短字符串的末尾。 返回前缀部分的字符串，即 str1 中的前
index 个字符。

复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

方式二：纵向扫描

思路

方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 获取第一个字符串的长度和数组的长度
        int length = strs[0].length();
        int count = strs.length;

        // 遍历第一个字符串的每个字符
        for (int i = 0; i < length; 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
25
26
27
28

说明：
longestCommonPrefix() 方法用于寻找字符串数组 strs 中的最长公共前缀。
如果字符串数组为空或长度为0，直接返回空字符串。 获取第一个字符串的长度和字符串数组的长度。 遍历第一个字符串的每个字符。 获取当前字符
c，用来与其他字符串的对应位置字符进行比较。 遍历剩余的字符串，依次比较当前字符和其他字符串对应位置的字符。
如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分，即第一个字符串的从索引0到当前位置的子串。
返回第一个字符串作为最长公共前缀，因为该字符串是其他字符串的公共前缀。

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 函数声明
char* longestCommonPrefix(char** strs, int strsSize);
char* commonPrefix(char* str1, char* str2);

/**
int main() {
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;

    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);

    // 释放内存
    free(result);

    return 0;
}
**/
/*
 * 获取字符串数组中的最长公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的大小
 * 返回值: 最长公共前缀的指针
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或者大小为0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 字符串数组的第一个字符串
    char* firstStr = strs[0];

    // 获取第一个字符串的长度
    int length = strlen(firstStr);

    // 遍历第一个字符串的每个字符
    for (int i = 0; i < length; i++) {
        char c = firstStr[i];
        
        // 遍历剩余的字符串进行比较
        for (int j = 1; j < strsSize; j++) {
            // 如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分
            if (i >= strlen(strs[j]) || strs[j][i] != c) {
                char* prefix = (char*)malloc((i + 1) * sizeof(char));
                strncpy(prefix, firstStr, i);
                prefix[i] = '\0';
                return prefix;
            }
        }
    }

    // 返回第一个字符串作为最长公共前缀
    return strdup(firstStr);
}

/*
 * 获取两个字符串的最长公共前缀的公共前缀
 * 参数: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最长公共前缀的指针
 */
char* commonPrefix(char* str1, char* str2) {
    int length1 = strlen(str1);
    int length2 = strlen(str2);

    int index = 0;
    // 比较两个字符串对应位置的字符
    while (index < length1 && index < length2 && str1[index] == str2[index]) {
        index++;
    }

    // 创建新的字符串，存储公共前缀
    char* result = (char*)malloc((index + 1) * sizeof(char));
    strncpy(result, str1, index);
    result[index] = '\0';

    return result;
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

说明
longestCommonPrefix() 函数用于找到字符串数组中的最长公共前缀。
首先判断字符串数组是否为空或大小为0。如果是，则直接返回空字符串。 获取字符串数组的第一个字符串 firstStr，并保存它的长度
length。 遍历第一个字符串的每个字符，并与剩余字符串的对应位置的字符进行比较，找到最长公共前缀。
如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，就返回前缀部分。使用malloc()
函数动态分配内存，使用strncpy() 函数复制字符串，并在末尾添加结束符 ‘\0’，然后返回前缀字符串的指针。
如果遍历后没有找到不相等的字符，说明第一个字符串是最长公共前缀，返回第一个字符串的拷贝，使用strdup() 函数实现。
commonPrefix() 函数用于获取两个字符串的最长公共前缀的公共前缀。
在循环中，比较两个字符串对应位置的字符，找到不相等的位置，返回前缀部分。这里使用了与之前相同的逻辑和函数。 main() 函数中调用了
longestCommonPrefix() 函数，并打印结果最长公共前缀。余下的是释放内存的代码，避免内存泄漏。

Python3版本

def longestCommonPrefix(strs):
    # 如果字符串数组为空或长度为0，直接返回空字符串
    if not strs:
        return ""

    # 字符串数组的第一个字符串
    firstStr = strs[0]

    # 遍历第一个字符串的每个字符
    for i in range(len(firstStr)):
        c = firstStr[i]

        # 遍历剩余的字符串进行比较
        for j in range(1, len(strs)):
            # 如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，返回前缀部分
            if i >= len(strs[j]) or strs[j][i] != c:
                return firstStr[:i]
    
    # 返回第一个字符串作为最长公共前缀
    return firstStr

# 调用函数并打印结果
#strs = ["flower", "flow", "flight"]
#result = longestCommonPrefix(strs)
#print("Longest Common Prefix:", result)

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

说明： longestCommonPrefix() 函数用于找到字符串数组中的最长公共前缀。
首先判断字符串数组是否为空。如果为空，则直接返回空字符串。 获取字符串数组的第一个字符串 firstStr。
遍历第一个字符串的每个字符，并与剩余字符串的对应位置的字符进行比较，找到最长公共前缀。
如果当前字符已经超过了某个字符串的长度，或者当前字符不等于其他字符串对应位置的字符，就返回前缀部分。 返回第一个字符串作为最长公共前缀。 在
main() 函数中，调用 longestCommonPrefix() 函数，并打印结果最长公共前缀。

复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

方式三：分治

思路

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或者长度为0，直接返回空字符串
        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());

        // 对比两个字符串的字符，找到不相等的位置，返回前缀部分
        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
45

说明：
longestCommonPrefix() 方法是递归函数，用于求取指定范围内字符串数组 strs 的最长公共前缀。
如果范围内只有一个字符串，则直接返回该字符串作为最长公共前缀。 否则，计算范围中间索引 mid。 调用递归函数
longestCommonPrefix() 分别求取左半部分和右半部分的最长公共前缀：lcpLeft 和 lcpRight。
返回左半部分和右半部分的最长公共前缀的公共前缀，即调用 commonPrefix() 函数。 commonPrefix()
方法用于求取两个字符串 lcpLeft 和 lcpRight 的最长公共前缀的公共前缀。 获取两个字符串的长度的最小值作为最小长度minLength。 逐个字符比较两个字符串的对应位置的字符，找到不相等的位置，返回当前位置前的子串作为最长公共前缀的公共前缀。
如果没有找到不相等的位置，返回最小长度范围内的字符串，即最长公共前缀。

C语言版本

#include <stdio.h>
#include <string.h>

// 函数声明
char* longestCommonPrefix(char** strs, int strsSize);

/*
 * 获取两个字符串的最长公共前缀
 * 参数: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最长公共前缀的指针
 */
char* commonPrefix(char* str1, char* str2);
/*
 * 获取字符串数组中的最长公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度
 * 返回值: 最长公共前缀的指针
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或者长度为0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 将第一个字符串作为初始的最长公共前缀
    char* prefix = strs[0];

    // 遍历剩余的字符串
    for (int i = 1; i < strsSize; i++) {
        // 更新最长公共前缀为当前遍历的字符串与最长公共前缀的公共前缀
        prefix = commonPrefix(prefix, strs[i]);

        // 如果最长公共前缀为空，说明不存在公共前缀，直接跳出循环
        if (strlen(prefix) == 0) {
            break;
        }
    }

    return prefix;
}

/*
 * 获取两个字符串的最长公共前缀的公共前缀
 * 参数: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最长公共前缀的指针
 */
char* commonPrefix(char* str1, char* str2) {
    int length1 = strlen(str1);
    int length2 = strlen(str2);

    int index = 0;
    while (index < length1 && index < length2 && str1[index] == str2[index]) {
        index++;
    }

    // 创建新的字符串，存储公共前缀
    char* result = (char*)malloc((index + 1) * sizeof(char));
    strncpy(result, str1, index);
    result[index] = '\0';  // 末尾添加结束符

    return result;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

说明：
longestCommonPrefix()函数用于找到字符串数组中的最长公共前缀。
在函数中，首先判断字符串数组是否为空或长度为0。如果是，则直接返回空字符串。 将字符串数组的第一个字符串作为初始的最长公共前缀prefix。
使用一个循环遍历剩余的字符串，分别与当前最长公共前缀进行比较，更新最长公共前缀。 如果最长公共前缀为空字符串，说明不存在公共前缀，跳出循环。
返回最长公共前缀prefix的指针。 commonPrefix()函数用于找到两个字符串的最长公共前缀的公共前缀。
在函数中，通过计算两个字符串的长度，初始化索引index为0。
使用一个循环比较两个字符串的对应位置字符，直到遇到不相等的字符或其中一个字符串的结尾。
创建一个新的字符数组result，用于存储公共前缀部分。 使用strncpy()函数将公共前缀部分复制到result中。
在result末尾添加结束符\0。 返回公共前缀result的指针。
请注意，使用malloc()动态分配了内存空间来存储结果字符串，因此在使用完毕后，记得使用free()函数释放它。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 定义递归函数，用于求取字符串数组中指定范围内的最长公共前缀
        def lcp(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
22
23
24
25
26

说明：
使用分治法，将指定范围划分为左右两部分，分别求取它们的最长公共前缀。 计算中间索引 mid。 调用 lcp()
函数求取左半部分的最长公共前缀 lcpLeft。 调用 lcp() 函数求取右半部分的最长公共前缀 lcpRight。
找到左右两部分最长公共前缀的最小长度。 在最小长度范围内逐个字符比较左右两部分的对应位置字符。
如果遇到第一个不相等的字符，返回当前位置前的子串作为最长公共前缀。 返回最小长度范围内的最长公共前缀。 如果字符串数组为空，则返回空字符串。
否则，调用 lcp() 函数，传入起始索引0和结束索引 len(strs) - 1，求取整个字符串数组的最长公共前缀。
longestCommonPrefix() 方法是主函数，用于启动递归过程并处理边界情况。lcp() 函数是一个内部递归函数，用于求取字符串数组中指定范围内的最长公共前缀

复杂度分析

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。时间复杂度的递推式是 T(n)=2⋅T(2n )+O(m)，通过计算可得 T(n)=O(mn)。
• 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 logn，每层需要 m 的空间存储返回结果。

方式四：二分查找

思路

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

代码实现

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空或长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // 获取字符串数组中最短字符串的长度
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        
        // 使用二分查找的思路来查找最长公共前缀
        int low = 0, high = minLength;
        while (low < high) {
            // 取中间位置
            int mid = (high - low + 1) / 2 + low;
            
            // 判断中间位置的前缀是否是公共前缀
            if (isCommonPrefix(strs, mid)) {
                // 如果是，更新 low，继续查找右半部分
                low = mid;
            } else {
                // 如果不是，更新 high，继续查找左半部分
                high = mid - 1;
            }
        }
        
        // 返回最长公共前缀
        return strs[0].substring(0, low);
    }
    
    // 判断指定长度前缀是否是字符串数组的公共前缀
    public boolean isCommonPrefix(String[] strs, int length) {
        // 获取第一个字符串的指定长度前缀
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        
        // 遍历剩余的字符串，逐个比较前缀字符
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        
        // 返回是否是公共前缀的结果
        return true;
    }
}
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
45
46
47
48
49
50
51
52
53

说明：
longestCommonPrefix() 方法用于求取字符串数组 strs 中的最长公共前缀。
首先判断字符串数组是否为空或长度为0，如果是，则直接返回空字符串。 获取字符串数组中最短字符串的长度 minLength。
使用二分查找的思路来查找最长公共前缀。 维持一个区间 [low, high]，初始为 [0, minLength]。
在每一次循环中，取区间的中间位置 mid。 判断以mid长度作为前缀是否是字符串数组的公共前缀，通过调用 isCommonPrefix()
方法实现。 如果是公共前缀，则更新 low = mid，继续查找右半部分。 如果不是公共前缀，则更新 high = mid -
1，继续查找左半部分。 当 low >= high 时，二分查找结束，得到最长公共前缀的长度。 返回最长公共前缀，使用
strs[0].substring(0, low) 来截取对应长度的前缀。 isCommonPrefix()
方法用于判断指定长度的前缀是否是字符串数组 strs 的公共前缀。 获取第一个字符串的指定长度前缀 str0。
遍历剩余的字符串，逐个比较前缀中的字符。 如果存在不相等的字符，说明不是公共前缀，返回 false。
如果所有字符串的前缀字符都相等，说明是公共前缀，返回 true。

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 函数声明
char* longestCommonPrefix(char** strs, int strsSize);
int isCommonPrefix(char** strs, int strsSize, int len);

/**
int main() {
    // 测试数据
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;

    // 调用函数并打印结果
    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);

    return 0;
}
**/
/*
 * 获取字符串数组中的最长公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度
 * 返回值: 最长公共前缀的指针
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空或长度为0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 找出最短字符串的长度
    int minLength = INT_MAX;
    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLength) {
            minLength = len;
        }
    }

    // 使用二分法查找最长公共前缀
    int low = 1;
    int high = minLength;
    int mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (isCommonPrefix(strs, strsSize, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // 根据最长公共前缀的长度，创建并返回结果字符串
    char* result = (char*)malloc((mid + 1) * sizeof(char));
    strncpy(result, strs[0], mid);
    result[mid] = '\0';

    return result;
}

/*
 * 判断指定长度前缀是否是字符串数组的公共前缀
 * 参数: strs - 字符串数组, strsSize - 字符串数组的长度, len - 前缀长度
 * 返回值: 是否是公共前缀的整数值，1为是，0为否
 */
int isCommonPrefix(char** strs, int strsSize, int len) {
    for (int i = 0; i < len; i++) {
        char ch = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != ch) {
                return 0;
            }
        }
    }
    return 1;
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

说明：
longestCommonPrefix()函数用于找到字符串数组中的最长公共前缀。
在函数中，首先判断字符串数组是否为空或长度为0。如果是，则直接返回空字符串。 找出字符串数组中最短字符串的长度minLength。
使用二分法来查找最长公共前缀。 初始化low为1，high为最短字符串的长度minLength。 循环遍历，直到找到最长公共前缀的长度。
设置mid为low和high的中间值。 如果前缀长度为mid的前缀是字符串数组的公共前缀，则在[mid+1, high]范围继续查找。
如果前缀长度为mid的前缀不是字符串数组的公共前缀，则在[low, mid-1]范围继续查找。
根据最长公共前缀的长度mid，动态分配内存创建结果字符串result。
使用strncpy()函数将字符串数组的第一个字符串的前mid个字符复制到结果字符串中。 在结果字符串的末尾添加结束符’\0’。
返回结果字符串的指针。 请注意，在使用完结果字符串后，不要忘记使用free()函数释放分配的内存。

Python3版本

def longestCommonPrefix(strs):
    # 如果字符串数组为空或长度为0，直接返回空字符串
    if not strs:
        return ""

    # 找出最短字符串的长度
    minLength = min(len(s) for s in strs)

    # 使用二分法查找最长公共前缀
    low = 1
    high = minLength
    while low <= high:
        mid = (low + high) // 2
        if isCommonPrefix(strs, mid):
            low = mid + 1
        else:
            high = mid - 1

    # 根据最长公共前缀的长度，返回结果字符串
    return strs[0][:low]

def isCommonPrefix(strs, length):
    for i in range(length):
        ch = strs[0][i]
        for j in range(1, len(strs)):
            if strs[j][i] != ch:
                return False
    return True

# 调用函数并打印结果
#strs = ["flower", "flow", "flight"]
#result = longestCommonPrefix(strs)
#print("Longest Common Prefix:", result)

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

说明：
longestCommonPrefix() 函数用于找到字符串数组中的最长公共前缀。
首先判断字符串数组是否为空。如果为空，则直接返回空字符串。 找出字符串数组中最短字符串的长度 minLength，使用 min()函数和生成器表达式来实现。 使用二分法来查找最长公共前缀。 初始化 low 为 1，high 为最短字符串的长度 minLength。
循环遍历，直到找到最长公共前缀的长度。 设置 mid 为 low 和 high 的中间值。 如果前缀长度为 mid
的前缀是字符串数组的公共前缀，则在 [mid+1, high] 范围继续查找。 如果前缀长度为 mid 的前缀不是字符串数组的公共前缀，则在[low, mid-1] 范围继续查找。 根据最长公共前缀的长度 low，返回结果字符串，使用切片操作实现。
isCommonPrefix() 函数用于判断指定长度的前缀是否是字符串数组的公共前缀。
使用嵌套循环遍历前缀的每个字符，逐个比较所有字符串的对应位置字符。 如果存在不相等的字符，说明不是公共前缀，返回 False。
如果所有字符串的前缀字符都相等，说明是公共前缀，返回 True。 调用函数并打印结果，使用示例字符串数组。

复杂度分析

• 时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

总结

其中，m 为字符串的平均长度，n 为字符串数组的长度，k 为字符串数组中的字符串字符最大长度。需要注意的是，在实际应用中，具体优化技巧和实现方法可能会对复杂度产生影响。因此，上述复杂度分析仅提供了一般情况下的大致估计。

相似题目