每日一刷：最长公共前缀
自言自语
题目来源于leetcode，每日一刷小算法。
不管遇到什么挫折，明天的太阳都会照样升起
题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例1
输入: ["flower","flow","flight"] 输出: "fl"
示例2
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
说明
所有输入只包含小写字母 a-z 。
思路
暴力解法
首先使用for循环让数组遍历。在这个循环中，让每个字符串里面的字符一一对比，直到对比到不相同的字符就退出。然后在这个不同的位置上切割，把前面相同的部分取出来。把取出来的这部分拿到跟下一个字符串对比。
例如：["lexinhu","lexinw","lexi"]
让前两个字符串中两个字符一一对比（可以用到while循环），到h和w这两个不同的位置时跳出循环，截取lexin，让lexin与lexi对比，截取到lexi，返回lexi即可。
Java自带的方法
针对上面的思路，我们可以用Java-String中的startWith()方法，判断第二个字符串是否以第一个字符串开头，如果不是，让第一个字符串裁剪掉一个尾部字符，继续对比。
例如：["lexinhu","lexinw","lexi"]
使用lexinhu与lexinw对比，不同时，lexinhu裁剪掉u，剩下lexinh，继续对比，直到lexin，刚好lexinw是以这个开头的，此时这个公共部门就是lexin，跟第三个字符lexi对比，执行相同的操作。
代码实现
暴力解
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String s = strs[0];
for (int i = 1; i < strs.length; i++) {
int index = 0;
while (
index < (Math.min(s.length(),strs[i].length()))
&& s.charAt(index) == strs[i].charAt(index)
){
index++;
}
s = strs[i].substring(0, index);
if(s.length() == 0){
return s;
}
}
return s;
}
}优化后
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String s = strs[0];
for (int i = 1; i < strs.length; i++) {
while(!strs[i].startsWith(s)){
s = s.substring(0, s.length()-1);
}
}
return s;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录