一、题目描述
======
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl" 示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
二、思路分析
======
纵向对比法
fl
。public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
int minLength = strs[0].length();
String firstStr = strs[0];
for (int i = 1; i < strs.length; i++) {
minLength = Math.min(minLength, strs[i].length());
if (minLength == 0) {
return "";
}
}
for (int i = 0; i < minLength; i++) {
for (int j = 1; j < strs.length; j++) {
if (firstStr.charAt(i) != strs[j].charAt(i)) {
return firstStr.substring(0, i);
}
}
}
return firstStr.substring(0, minLength);
}
动态规划法
f(x)\=g(g(g(str[0],str[1]),str[2])....,str[x])f(x) = g(g(g(str[0],str[1]),str[2])....,str[x])f(x)\=g(g(g(str[0],str[1]),str[2])....,str[x])
f(x+1)\=g(x+1,f(x))f(x+1)=g(x+1,f(x))f(x+1)\=g(x+1,f(x))
public String longestCommonPrefix2(String[] strs) {
if (strs.length == 0) {
return "";
}
String longest = strs[0];
for (int i = 1; i < strs.length; i++) {
if (longest.length() == 0) {
return "";
}
longest = longestFromTwo(longest, strs[i]);
}
return longest;
}
public String longestFromTwo(String a, String b) {
int length = Math.min(a.length(), b.length());
for (int i = 0; i < length; i++) {
if (a.charAt(i) != b.charAt(i)) {
return a.substring(0, i);
}
}
return a.substring(0, length);
}
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。