题目来源于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;
}
}
版权属于:乐心湖's Blog
本文链接:https://www.xn2001.com/archives/504.html
声明:博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!