Algorithm

[LeetCode 14] Longest Common Prefix [C] [Runtime : 3 MS]

顿搜

2017-06-07

0 评论

724 阅读

正在检测是否收录...

06/07

1. Description

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

2. Example

{"a","a","b"} should give "" as there is nothing common in all the 3 strings.
{"a", "a"} should give "a" as a is longest common prefix in all the strings.
{"abca", "abc"} as abc
{"ac", "ac", "a", "a"} as a

3. Code

char* longestCommonPrefix(char** strs, int strsSize) {

    int str0_length = strsSize == 0 ? 0 : strlen(strs[0]);

    int i = 0, is_find = 0;
    for (; i < str0_length && !is_find; i++ )
    {
        for (int j = 1; j < strsSize && !is_find; j++)
        {
            if (strs[0][i] != strs[j][i])
            {
                i--; is_find = 1;
            }
        }
    }

    char *result = (char*)malloc((i + 1) * sizeof(char));
    strncpy(result, strs[0], i);
    result[i] = '\0';
    return result;
}

4.Test

#include<stdio.h>

char* longestCommonPrefix(char** strs, int strsSize) {

    int str0_length = strsSize == 0 ? 0 : strlen(strs[0]);

    int i = 0, is_find = 0;
    for (; i < str0_length && !is_find; i++ )
    {
        for (int j = 1; j < strsSize && !is_find; j++)
        {
            if (strs[0][i] != strs[j][i])
            {
                i--; is_find = 1;
            }
        }
    }

    char *result = (char*)malloc((i + 1) * sizeof(char));
    strncpy(result, strs[0], i);
    result[i] = '\0';
    return result;
}

int main()
{
    char *strs[] = { "a","b" };
    puts(longestCommonPrefix(strs, 2));
    system("pause");
    return 0;
}