LeetCode笔记:14. Longest Common Prefix
2023-03-15 23:20:40 时间
问题
Write a function to find the longest common prefix string amongst an array of strings.
大意:
写一个函数来寻找一个数组的字符串中最长的相同前缀。
思路:
题目描述很简单只有一句话,导致我理解错了,以为是找到存在的任意两个字符串最长的相同前缀,还写了一份代码出来,自己测试的时候发现题目想要的结果不符合才发现,其实是找整个数组的字符串都有的相同的最长前缀,这就方便多了。
我采用从第一个字符串的前头开始一个一个地增加前缀长度来判断后面所有的字符串是否有同样的前缀,然后返回结果。
在这个过程中有很多特殊情况要注意,比如如果数组长度为0,直接返回空字符串;如果只有一个字符串,直接返回该字符串;如果存在某个字符串(包括第一个)就是“”这样的空字符串,直接返回“”;每次增加前缀长度的时候要判断第一个字符串是否够长,不够了就直接返回当前结果;只有当所有后面的字符串都存在前缀时才可以认为是相同的,只要有一个不相同就可以直接返回之前已经记录的前缀了等等。
代码(Java):
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
else if (strs.length == 1) return strs[0];
int end = 1;
String result = "";
String firstStr = strs[0];
if (firstStr.length() == 0) return "";
else {
String sub;
while (end <= firstStr.length()) {
sub = firstStr.substring(0, end);
for (int i = 1; i < strs.length; i++) {
String nowStr = strs[i];
if (nowStr.length() == 0) return "";
else {
if (nowStr.startsWith(sub, 0)) {
if (i == strs.length-1) {
result = sub;
end ++;
}
} else return result;
}
}
}
}
return result;
}
}
他山之石:
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String pre = strs[0];
for (int i = 1; i < strs.length; i++)
while(strs[i].indexOf(pre) != 0) {
pre = pre.substring(0,pre.length()-1);
if (pre.length() == 0) return "";
}
return pre;
}
}
这个做法是先用整个第一个字符串来当做前缀去判断每个字符串是否拥有该前缀,没有就将这个判断的前缀末尾字符去掉再比较,直到当前判断的字符串有这个前缀了,才去判断下一个字符串有没有,执行同样的操作。当任何时候前缀长度减少到0了,也可以直接返回了。这个做法会快一点,而且免去了很多特殊情况的判断,代码很简洁。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十