1. 题目描述
2. 解题思路
对于一个数组的常规处理思路一般都是先遍历数组，取出其中的字符串再进行操作，后来瞅了一眼官解中把这种方法命名为横向扫描（反正我自己是没想出来这个命名）。这种思路是最简单的思路，我以数组中的第一个字符串为最长公共前序对比基准，不符合则退一位。
最开始敲码的时候第一反应就是把字符串转换成字符数组，再进行字符的比较，提交后发现这个算法占用的储存空间不太理想（废话，多了两个数组肯定不理想），翻了一下发现String类有个charAt()方法（当时已经完全忘掉了），可以直接取字符串中的字符，然后优化了一下储存空间果然理想了一点。
当有了基本思路之后开始想一些骚操作了，既然可以对每个字符串进行一一扫描比较，那么我也可以先对所有字符串中的字符进行一一逐位比较，这种方法在官解中也有，被称为纵向扫描。可能有点难理解，有兴趣的可以去看看官解的配图，这里就不贴了。
除此以外，还有什么方法吗？其实还是有的，横向扫描常规肯定是对字符串进行从前往后扫，我们可以反其道而行之，对当前记录的最大公共前缀索引开始从后往前扫描比较。
3. 代码实现
3.1 横向扫描
public String longestCommonPrefix(String[] strs) {
char[] chars = strs[0].toCharArray();
int length = chars.length;
int min = length;
int s = 0;
for (int i = 1; i < strs.length; i++) {//遍历数组
char[] chars1 = strs[i].toCharArray();
int length1 = chars1.length;
for (int i1 = 0; i1 < min(length, length1); i1++) {//遍历字符串
if (chars[i1] == chars1[i1]) {
s++;
} else {
break;
}
}
if (s < min) {
min = s;
}
s = 0;
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < min; i++) {
stringBuilder.append(chars[i]);
}
return new String(stringBuilder);
}
private int min(int length, int length1) {
if (length < length1)
return length;
else
return length1;
}
3.2 横向扫描（优化储存）
public String longestCommonPrefix(String[] strs) {
int length = strs[0].length();
int min = length;
int s = 0;
int length1;
for (int i = 1; i < strs.length; i++) {//遍历数组
length1 = strs[i].length();
for (int i1 = 0; i1 < min(length, length1); i1++) {//遍历字符串
if (strs[0].charAt(i1) == strs[i].charAt(i1)) {
s++;
} else {
break;
}
}
if (s < min) {
min = s;
}
s = 0;
}
return strs[0].substring(0, min);
}
private int min(int length, int length1) {
if (length < length1)
return length;
else
return length1;
}
该种算法为所尝试算法中的最优：
3.3 纵向扫描
public String longestCommonPrefix(String[] strs) {
for (int i = 0; i < strs[0].length(); i++) {//遍历字符串
for (String str : strs) {//遍历数组
try {
if (str.charAt(i) != strs[0].charAt(i))
return strs[0].substring(0, i);
}catch (Exception e){
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
3.4 横向扫描（逆序）
public String longestCommonPrefix(String[] strs) {
int maxIndex = strs[0].length() - 1;
int rr;
for (int i = 1; i < strs.length; i++) {//遍历数组
if (strs[i].length() - 1 < maxIndex) {
maxIndex = strs[i].length() - 1;
}
rr = maxIndex;
while (rr >= 0) {//遍历字符串
if (strs[0].charAt(rr) != strs[i].charAt(rr)) {
maxIndex = rr-1;
}
rr--;
}
}
return strs[0].substring(0, maxIndex + 1);
}
3.5 对比
可以看出，几种算法的运行时间并没有什么变化，因为他们的时间复杂度都是O(mn)，m为数组长度，n为字符串长度。因此，即使包括官解中的二分法和分治等方法也不会有明显的改变（虽然我想不出来），个人感觉只是为了炫技的存在，对时间复杂度也没有进行优化。
