题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
说明:所有输入只包含小写字母 a-z 。
示例
示例1：
| 1 2 3 | 输入: ["flower","flow","flight"] 输出: "fl" |
示例2：
| 1 2 3 4 | 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 |
题目解析
我的思路是，首先对所有的字符串进行排序，因为存入了vector，所以直接使用sort排序即可。然后，寻找第一个字符串和最后一个字符串的最大公共前缀，就是整个数组的公共前缀。
当然，要考虑一些特殊情况：
1. 数组中是一个或一个以上空字符串。
2. 数组为空。
具体解决方法在下面的代码已经体现。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | string longestCommonPrefix(vector<string>& strs) { string res; int strslen = strs.size(); if (strslen < 1) return res; else if (strslen == 1) return strs[0]; sort(strs.begin(), strs.end()); int i = 0; for (int i = 0; i < strslen; i++) { if (strs[i].size() == 0) return res; } int llen = strs[0].size(); int rlen = strs[strslen - 1].size(); int mlen = min(llen, rlen);//保证比较最小的长度 while (strs[0][i] == strs[strslen - 1][i]) { res += strs[0][i]; if (i < mlen)//如果已经达到最小长度就退出 ++i; else break; } return res; } |
