---
title: 'LeetCode 14. Longest Common Prefix'
disqus: hackmd
---

# LeetCode 14. Longest Common Prefix

## Description

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

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

## Constraints

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.

## Answer

先計算最小長度，因為答案頂多和最小長度一樣，再來用雙層while，外層跑第幾個字元，內層跑第幾個字串，所以先檢查各自串的第j個字元是否相同，若都一樣就會將cnt數到strsSize，如此就往下個j移動，若有不同就直接跳出。最後將strs[0]的前j個字元準備成ans即可。

char * longestCommonPrefix(char ** strs, int strsSize){
    int i = 0, j = 0, k = 0, cnt = 0, siz = strlen(strs[0]), flag = 1;
    for(k = 1; k < strsSize; k++){
        siz = siz < strlen(strs[k]) ? siz : strlen(strs[k]);
    }
    while(flag && i < siz){
        for(j = 0; j < strsSize; j++){
            if(strs[0][i] != strs[j][i]){
                flag = 0;
            }
        }
        if(flag){cnt = i + 1;i++;}
    }
    char *ans = (char*)malloc(sizeof(char)*(cnt+1));
    ans[cnt] = '\0';
    for(i = 0; i < cnt; i++){
        ans[i] = strs[0][i];
    }
    return ans;
}

## Link
https://leetcode.com/problems/longest-common-prefix/
###### tags: `Leetcode`