最长公共前缀(longest-common-prefix)
最长公共前缀 (longest-common-prefix)
题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入: [“flower”,“flow”,“flight”]
输出: “fl”
示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
循环比较法
package longest_common_prefix;
public class Solution {
/**最长公共前缀*/
public String longestCommonPrefix(String[] strs) {
if(strs.length==0) {
return "";
}
if(strs.length==1) {
return strs[0];
}
//准备两个字符串数组,用于比较,第一个是固定的,第二个是变动的
final char[] str1 = strs[0].toCharArray();
char[] str2;
//准备第一个字符串的长度
int length = str1.length;
//循环输入的string数组
for(int i=0;i<strs.length-1;i++) {
//拿出一个来,跟第一个比较
str2 = strs[i+1].toCharArray();
if(str2.length==0) {
return "";
}
for(int x=0,y=0;x<length && y<str2.length;x++,y++) {
//如果不相等,则跳出循环
if(str1[x]!=str2[y]) {
length=x;
break;
}else {
//如果相等,就判断一下边界,到达边界,则跳出循环
if(x==length-1 || y==str2.length-1) {
length = Math.min(length, str2.length);
break;
}
}
}
if(length==0) {
return "";
}
}
//返回最长公共前缀
StringBuffer bf = new StringBuffer();
for(int i=0;i<length;i++) {
bf.append(str1[i]);
}
return bf.toString();
}
public static void main(String[] args) {
String[] ss = {"flower","flow","fligtht"};
Solution solu = new Solution();
System.out.println(solu.longestCommonPrefix(ss));
}
}
其实,是否相等判断和边界检查可以放在同一层判断
//如果不相等,则跳出循环
if(str1[x]!=str2[y]) {
length=x;
break;
}else {
//如果相等,就判断一下边界,到达边界,则跳出循环
if(x==length-1 || y==str2.length-1) {
length = Math.min(length, str2.length);
break;
}
}
可以变成这样
if(str1[x]!=str2[y]){
length=x;
break;
}else if(x==length-1 || y==str2.length-1){
length = Math.min(length,str2.length);
}
减尾巴法
public String longestCommonPrefix_2(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 String longestCommonPrefix_3(String[] strs) {
if (strs.length == 0) return "";
for(int i=0;i<strs[0].length();i++){
char c = strs[0].charAt(i);
for(int j=1;j<strs.length;j++){
//边界检查和字符是否相等判断放在同一层
if(i==strs[j].length() || c!=strs[j].charAt(i)){
return strs[0].substring(0,i);
}
}
}
return strs[0];
}
方法三:分治
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return longestCommonPrefix(strs, 0 , strs.length - 1);
}
private String longestCommonPrefix(String[] strs, int l, int r) {
if (l == r) {
return strs[l];
}
else {
int mid = (l + r)/2;
String lcpLeft = longestCommonPrefix(strs, l , mid);
String lcpRight = longestCommonPrefix(strs, mid + 1,r);
return commonPrefix(lcpLeft, lcpRight);
}
}
String commonPrefix(String left,String right) {
int min = Math.min(left.length(), right.length());
for (int i = 0; i < min; i++) {
if ( left.charAt(i) != right.charAt(i) )
return left.substring(0, i);
}
return left.substring(0, min);
}
方法四:二分查找法
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
int minLen = Integer.MAX_VALUE;
for (String str : strs)
minLen = Math.min(minLen, str.length());
int low = 1;
int high = minLen;
while (low <= high) {
int middle = (low + high) / 2;
if (isCommonPrefix(strs, middle))
low = middle + 1;
else
high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);
}
private boolean isCommonPrefix(String[] strs, int len){
String str1 = strs[0].substring(0,len);
for (int i = 1; i < strs.length; i++)
if (!strs[i].startsWith(str1))
return false;
return true;
}
更进一步
public String longestCommonPrefix(String q, String[] strs) {
if (strs == null || strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
Trie trie = new Trie();
for (int i = 1; i < strs.length ; i++) {
trie.insert(strs[i]);
}
return trie.searchLongestPrefix(q);
}
class TrieNode {
// 子节点的链接数组
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
// 非空子节点的数量
private int size;
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
size++;
}
public int getLinks() {
return size;
}
// 假设方法 containsKey、isEnd、get、put 都已经实现了
// 可以参考文章:https://leetcode.com/articles/implement-trie-prefix-tree/
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 假设方法 insert、search、searchPrefix 都已经实现了
// 可以参考文章:https://leetcode.com/articles/implement-trie-prefix-tree/
private String searchLongestPrefix(String word) {
TrieNode node = root;
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
prefix.append(curLetter);
node = node.get(curLetter);
}
else
return prefix.toString();
}
return prefix.toString();
}
}
参考资料
关于字符串的算法题2:最长公共前缀,最长回文子串
14. 最长公共前缀
韩顺平-视频-归并排序算法思路图解