LEETCODE算法:14. Longest Common Prefix

发表于 更新于 分类于 Waline： 阅读次数：

题目

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.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//逐一比较，发现报错贴补丁，代码很丑
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0) return "";
        int res=INT_MAX;
        for(int i=0;i<strs.size()-1;i++)
        {
            if(strs[i].length()==0||strs[i+1].length()==0) return "";
            for(int j=0;j<min(strs[i].length(),strs[i+1].length());j++)
            {
                if(strs[i][j]!=strs[i+1][j]) {
                    res=min(res,j);
                    break;
                }else if(j==min(strs[i].length(),strs[i+1].length())-1){
                    res=min(res,j+1);
                }
            }
        }
        return strs[0].substr(0,res);
    }
};