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:

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) {
string res="";
if(strs.size()==0) return res;
if(strs.size()==1) return strs[0];
int j=0;
bool flag = false;
for(j;j<strs[0].size();j++)
{
for(int i=1;i<strs.size();i++)
{
if(strs[i-1][j]!=strs[i][j])
{
return res;
}
}
res +=strs[0][j];
}
return res;
}
};

题目链接

Longest Common Prefix