LeetCode --- 字符串、数组
简书专栏：https://www.jianshu.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416
一、题目描述
来源：力扣（LeetCode）
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
说明:
所有输入只包含小写字母 a-z 。
要求实现函数：
public String longestCommonPrefix(String[] strs) {}
二、实现思路以及代码
2.1 思路一：暴力破解法
先找出字符串数组中最短的字符串，记录其长度为min，以第一个字符串为基准，遍历长度为min,依次和字符串数组中的其他字符串相比较，如果都一样，则遍历下一位，一直到出现不同的字符为止，结束循环。
2.1.1 暴力破解实现代码
public static String longestCommonPrefix1(String[] strs) {
if (strs.length == 0) {
return "";
}
StringBuffer br = new StringBuffer();
//最短数组长度
int min = strs[0].length();
for(int i = 1; i < strs.length; i++) {
if (min > strs[i].length()) {
min = strs[i].length();
}
}
//匹配最短前缀
for(int j = 0; j< min; j++) {
char c = strs[0].charAt(j);
for(int k = 1; k < strs.length; k++) {
if(c != strs[k].charAt(j)){
return br.toString();
}
}
br.append(c);
}
return br.toString();
}
2.2 思路二：字符串巧解 水平扫描法
利用String类自带的函数indexOf()来进行数据处理，indexOf()函数返回的是目标字符串在当前字符串中所在的位置，如果当前字符串不存在目标字符串则返回-1。本算法实现思路是依次扫描字符串数组，以第一个字符串prefix为基准，如果后续字符串中prefix的位置不是在其初始位置，那么就对prefix进行从后向前缩减一个字符。可以理解为，prefix字符串和当前字符串取其从首字母开始的最长公共前缀，然后再求与下一个字符串的公共前缀，直到字符串数组遍历完成。其中，若prefix减为”“了，则表明没有共同前缀，直接返回。
该算法时间复杂度大大减少
2.2.1 水平扫描法实现代码
public static String longestCommonPrefix2(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
三、测试代码
public static void main(String[] args) {
String[] strs1 = {"hexlo", "helff", "hellx"};
String[] strs2 = {"hello", "ssss", "wfef"};
System.out.println(longestCommonPrefix1(strs1));
System.out.println(longestCommonPrefix1(strs2));
System.out.println(longestCommonPrefix2(strs1));
System.out.println(longestCommonPrefix2(strs2));
}
输出结果为：
he
he
