Longest Common Prefix

LeetCode笔记 阅读(51)

编号 : 14      
难度 : <font color="green">Easy</font>

# 题目 :  
>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.
>

# 解 :  
```Cpp
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ret = "";
        
        // strs.size() > 0 可以过滤掉空的输入
        for(size_t index = 0; strs.size() > 0 && index < strs[0].size(); index++)
        {
            // i+1 < strs.size() 跳过只有一个字符串的情况
            for(size_t i = 0; i+1 < strs.size(); i++)
            {
                if(index >= strs[i+1].size() ||
                   strs[i][index] != strs[i+1][index])
                {
                    return ret;
                }
            }
            ret += strs[0][index];
        }
        
        return ret;
    }
};
```

# 分析 :  
各个字符串上索引相同的字符逐个比较,直到存在字符不同或者某个字符串读完则结束返回,输入中没有或者只有一个字符串时,需要特殊处理。

Markdown使用 帮助