1. 题目描述

problem link

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

2. 解题

最长公共前缀，方法很多，我用的是“垂直扫描”。

即依次比较每个字符串的第1位、第2位 ... 直到出现某一位并不是所有字符串都相同，就找到了最长前缀，返回即可。具体写代码的时候，可以直接以strs[0]作为最终返回的结果，因为最长前缀最长也不可能超过strs[0]的长度，最后找到最长前缀后直接在对应位写上'\0'即可。

时间复杂度：O(S)，S是所有字符串字符数的和。可知在最坏情况下，所有字符串都完全相同，则需要比较S次。

类似的还有很多方法，例如“水平扫描”，即前两个字符串先找出一个最长公共前缀，在拿这个最长公共前缀和第三个字符串比较，依此类推。时间复杂度O(S)。

也可以用分治的思想，所有字符串两两比较找出一组最长公共前缀，再从这一组字符串中再两两比较再找出下一组最长公共前缀，依此类推最终得到总的最长公共前缀。时间复杂度O(S)。可知最坏情况第一次要比较 $ \frac{S}{2} $ 次，第二次要比较 $ \frac{S}{4} $ 次，依此类推最终时间复杂度O(S)。

最后还可以用前缀树这个数据结构，有关前缀树可以看这个文章：

可以稍微修改一下前缀树的数据结构，里面加上一个字段size表示这个节点下有多少个非空子节点，方便找公共前缀。然后在判断什么时候找到了公共前缀可以看下面这个图：

这个前缀树插入了"le" "lead" "leet"三个字符串，可知最长前缀为"le"，而判断找到最长前缀的条件有两个，一是当前节点的isEnd值为1，说明不可能有更长的公共前缀了，二是这个节点下面有不止一个非空子节点。

3. 代码

垂直扫描

char* longestCommonPrefix(char ** strs, int strsSize) {
    if (strsSize == 0) {
        return "";
    }
    if (strsSize == 1) {
        return strs[0];
    }

    for (int i = 0; i < strlen(strs[0]); i++) {  // 遍历strs[0]第i个字符
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {  // 和第strs[j]个字符串的第i个字符比较
            if (strs[j][i] != c || strs[j][i] == '\0') {
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }

    return strs[0];
}

前缀树

#define R 26  // 26个小写字母

typedef struct prefixTreeNode {
    struct prefixTreeNode* links[R];  // 每个节点26个分叉
    int size;  // 当前节点有几个非空子节点
    int isEnd;  // 0 or 1
} Node;

void nodeInit(Node** pRoot) {
    *pRoot = (Node *)malloc(sizeof(Node));
    for (int i = 0; i < R; i++) {
        (*pRoot)->links[i] = NULL;
    }
    (*pRoot)->isEnd = 0;
    (*pRoot)->size = 0;
}

void prefixTreeInsert(Node* root, char* str) {
    Node* cur = root;

    while (*str) {  // 取出str中每个字符
        if (cur->links[*str - 'a'] == NULL) {  // 如果这个字符不存在
            nodeInit(&(cur->links[*str - 'a']));
            cur->size++;
        }
        cur = cur->links[*str - 'a'];  // cur前进到下一层    
        str++;
    }
    cur->isEnd = 1;
}

// 返回当前节点有几个非空子节点
int getLinks(Node* pNode) {
    return pNode->size;
}

char * longestCommonPrefix1(char ** strs, int strsSize) {
    if (strsSize == 0) {
        return "";
    }
    if (strsSize == 1) {
        return strs[0];
    }

    // 前缀树初始化
    Node* root;
    nodeInit(&root);

    // 将所有字符串插入前缀树
    for (int i = 0; i < strsSize; i++) {
        prefixTreeInsert(root, strs[i]);
    }
    
    // 寻找最长公共前缀
    char* res = (char *)malloc(sizeof(char) * 1000);
    char* tmp = res;
    Node* cur = root;

    for (int i = 0; ; i++) {
        char c = strs[0][i];

        // 有两个条件表示已经找到了最长公共前缀，要跳出循环
        // 1. cur->isEnd = 1，表示有一个字符串终止在了这个字符
        // 2. cur下有不止一个子节点非空
        if (cur->isEnd != 1 && getLinks(cur) == 1) {
            *tmp++ = c;
            cur = cur->links[c - 'a'];
            continue;
        }
        break;
    }
    *tmp = '\0';

    return res;
}