返回目录

编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串""

1）示例1:
输入: ["flower","flow","flight"]
输出: "fl"
2）示例2:
输入: ["dog","ran","car"]
输出: ""

Python源码

def main():
    arr = ["flower", "flow", "flight"]
    print(solution(arr))

def solution(arr):
    first = arr[0]
    # 初始化一个空列表存储最长公共前缀
    list = []
    for i in range(1, len(first)):
        sub = first[:i]  # 获取从开头到第 i 个字符的子串
        flag = True
        for j in range(1, len(arr)):
            if not arr[j].startswith(sub):  # 如果不是以 sub 开头，将 flag 设为 False
                flag = False
                break
        if flag:
            list.append(sub)  # 如果所有字符串都以 sub 开头，则将其添加到列表中
    return list[-1] if list else ""  # 返回最长公共前缀，如果列表为空则返回空字符串

if __name__ == "__main__":
    main()

C语言源码

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

// 找到字符串数组的最长公共前缀
char* solution(char** arr, int n) {
    char* first = arr[0]; // 取第一个字符串作为基准
    char** list = NULL;   // 存储最长公共前缀的列表
    int count = 0;        // 列表中元素计数

    // 从第一个字符串中逐步增加字符，构建可能的前缀并检查
    for (int i = 1; i < strlen(first); i++) {
        char* sub = (char *)malloc((i + 1) * sizeof(char)); // 为子串分配内存
        strncpy(sub, first, i); // 复制子串
        sub[i] = '\0'; // 在子串末尾添加空字符，确保字符串终止

        int flag = 1; // 标志变量，用于检查是否满足前缀条件
        // 检查每个字符串是否以当前子串为前缀
        for (int j = 1; j < n; j++) {
            if (strncmp(arr[j], sub, i) != 0) {
                flag = 0; // 如果有一个不满足条件，则置 flag 为 0
                break;
            }
        }
        if (flag) {
            // 如果所有字符串都以当前子串为前缀，则将其添加到列表中
            list = (char **)realloc(list, (count + 1) * sizeof(char *));
            list[count] = sub;
            count++;
        } else {
            free(sub); // 如果子串不满足条件，则释放其内存
        }
    }

    if (count > 0) {
        // 如果列表中有元素，则返回最后一个元素作为最长公共前缀
        char* longest_prefix = list[count - 1];
        free(list); // 释放列表内存
        return longest_prefix;
    } else {
        // 如果列表为空，则返回空字符串
        free(list); // 释放列表内存
        char* empty_string = (char *)malloc(sizeof(char));
        empty_string[0] = '\0';
        return empty_string;
    }
}

int main() {
    char* arr[] = {"flower", "flow", "flight"};
    int n = sizeof(arr) / sizeof(arr[0]);
    char* longest_prefix = solution(arr, n);
    printf("%s\n", longest_prefix);
    free(longest_prefix); // 释放最长公共前缀内存
    return 0;
}

Java源码

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        String[] arr = {"flower", "flow", "flight"};
        System.out.println(solution(arr));
    }

    // 找到字符串数组的最长公共前缀
    private static String solution(String[] arr) {
        String first = arr[0]; // 取第一个字符串作为基准
        ArrayList<String> list = new ArrayList<>(); // 存储最长公共前缀的列表

        // 从第一个字符串中逐步增加字符，构建可能的前缀并检查
        for (int i = 1; i < first.length(); i++) {
            String sub = first.substring(0, i); // 获取子串
            boolean flag = true; // 标志变量，用于检查是否满足前缀条件
            // 检查每个字符串是否以当前子串为前缀
            for (int j = 1; j < arr.length; j++) {
                if (!arr[j].startsWith(sub)) {
                    flag = false; // 如果有一个不满足条件，则置 flag 为 false
                    break;
                }
            }
            if (flag) {
                // 如果所有字符串都以当前子串为前缀，则将其添加到列表中
                list.add(sub);
            }
        }

        if (!list.isEmpty()) {
            // 如果列表不为空，则返回列表中最后一个元素作为最长公共前缀
            return list.get(list.size() - 1);
        } else {
            // 如果列表为空，则返回空字符串
            return "";
        }
    }
}