【leetcode】14：最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母 a-z 。
解答
这道题还是比较简单的，不过简单的题，虽然你会做，不代表你能做的好。我觉得很多人可能会这样做：
1、先找出 str1 和 str2（注：str1代表第一个字符串，str2代表第二个） 的公共字符串 s1。
2、然后再找出 s1 和 str3 的公共前缀 s2。
3、然后再找出 s2 和 str4 的公共前缀 s3。
4、一直这样遍历重复，用一个变量来保存两个两个字符串之间的公共前缀。
这种方法应该是最容易想到的了，不过并不是特别好，其实我们可以这样做：我们不横向一个一个字符串遍历，而是采用纵向的方式。例如对于这个["flower","flow","flight"]。我们把它看成一个二维字符数组
f l o w e r
f l o w
f l i g h t然后纵向遍历，一列一列遍历，只要发现某一列出现不同的字符，就遍历结束，例如上面这个例子中，第三列就出现不同了，所以遍历结束，把前两列返回。代码如下：
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length <= 0) {
return "";
}
String s = "";
for (int j = 0; j < strs[0].length(); j++) {
char c = strs[0].charAt(j);
// 开始纵向遍历
for (int i = 1; i < strs.length; i++) {
if (j >= strs[i].length() || c != strs[i].charAt(j)) {
return s;
}
}
s += c;
}
return s;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录