leetcode14.最长公共前缀
Question
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ”“。
示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “fl”
示例 2: 输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Answer
package test001;
public class Test001 {
public String longestCommonPrefix(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);
//System.out.println(prefix);
if (prefix.isEmpty()) return "";
//如果修剪到prefix为空说明他们没有公共前缀，直接退出
}
return prefix;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Test001 a = new Test001();
String[] s = new String[] {"flower","lm","flight"};
System.out.println(a.longestCommonPrefix(s));
}
}
Attention
- 水平扫描法
以三个字符串的字符数组"flower","lm","flight"为例，先选择第一个字符串存为prefix，算法从第二个字符串开始。while循环内，flower不是lm的前缀，修建prefix，去掉尾部一位——>flowe，flowe仍然不是lm的前缀，再去掉一位，直到prefix为空直接退出。
while循环退出的条件：
1.两个字符串有公共前缀，修剪后返回prefix，如"flower","flow","flight"，flower与flow比较，flower修剪到flow时，prefix已经是flow的前缀，退出while循环，将prefix再与flight比较
2.prefix修剪为空了，返回空，不用继续比较后一个字符串了
- String.indexOf()用法
查找指定字符或字符串在字符串中第一次出现地方的索引，未找到的情况返回 -1.
String str1="012345";
String str2="23";
System.out.println( str1.indexOf(str2) );
输出2
- 复杂度分析
