Write a function to find the longest common prefix string amongst an array of strings.
這道題的要求是在字符串數組中找到最長公共前綴。
思路比較簡單,就是兩個字符串逐個比較,找最長公共子串。這裡采用將每個字符串都與第一個字符串相比較,求最長子串。
時間復雜度:O(nm)(n是字符串數組長度,m是字符串長度)
空間復雜度:O(1)
1 class Solution
2 {
3 public:
4 string longestCommonPrefix(vector &strs)
5 {
6 if(strs.size() == 0)
7 return ;
8
9 string pre = strs[0];
10 for(int i = 1, j; i < strs.size(); ++ i)
11 {
12 for(j = 0; j < pre.size() && j < strs[i].size(); ++ j)
13 if(pre[j] != strs[i][j])
14 break;
15 pre = pre.substr(0, j);
16 }
17 return pre;
18 }
19 };