Write a function to find the longest common prefix string amongst an array of strings.
这道题的要求是在字符串数组中找到最长公共前缀。
思路比较简单,就是两个字符串逐个比较,找最长公共子串。这里采用将每个字符串都与第一个字符串相比较,求最长子串。
时间复杂度:O(nm)(n是字符串数组长度,m是字符串长度)
空间复杂度:O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
public:
string longestCommonPrefix(vector<string> &strs)
{
if(strs.size() == 0)
return "";
string pre = strs[0];
for(int i = 1, j; i < strs.size(); ++ i)
{
for(j = 0; j < pre.size() && j < strs[i].size(); ++ j)
if(pre[j] != strs[i][j])
break;
pre = pre.substr(0, j);
}
return pre;
}
};