Longest Common Prefix问题

Longest Common Prefix问题

leetcode

java

1.问题描述

Write a function to find the longest common prefix string amongst an array of strings.
题目翻译：
写一个函数，找到一个String数组中各个字符串的最长公共前缀。

2.解题思路

这道题的难度是easy，确实解题思路也比较直观，首先找到前两个字符串的最长公共前缀，然后再利用这个公共前缀和后面的字符串进行比对得到最长公共前缀，依次比对下去，就能得到最长的公共前缀，中间只要一步没有公共前缀，就返回空的字符串。

3.代码实现

1. 第一种实现：

class Solution {
	public String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        String res = "";
        if(strs==null||len==0) {//判断是否为空
        	return res;
        }
        if(len==1)//当只有一个字符串
            return strs[0];
        //char[] ch1 = strs[0].toCharArray();
        int len1=0,len2=0;
        len1 = compareStr(strs[0],strs[1]);//首先比较最开始的两个
        if(len1==0)
        	return "";//为空就返回
        else
        	res = strs[0].substring(0, len1);//注意substring的用法
        
        for(int i=1;i<=len-1;i++) {
        	int tmp = compareStr(res,strs[i]);//依次比较前缀和下一个字符串
        	if(tmp==0)
        		return "";
        	else
        		res = res.substring(0,tmp);//更新前缀
        }
        return res;
    }
	
	public  int compareStr(String s1,String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		int res=0;
		if(len1==0||len2==0)
			return 0;
		 char[] ch1 = s1.toCharArray();
		 char[] ch2=s2.toCharArray();
		 
		 int com_len = len1>len2?len2:len1;
		 for(int i=0;i<com_len;i++) {
			 if(ch1[i] == ch2[i])
				 res++;
			 else
				 break;
		 }
		 return res;//返回前缀的长度
	}
}

2. 第二种实现

class Solution {
public String longestCommonPrefix(String[] strs) 
  {
       if(strs.length==0) return "";
       if(strs.length==1) return strs[0];
       String prefix=strs[0];//初始化prefix为第一个字符串
      
       for(int i=1;i<strs.length;i++)
       {  //利用循环依次判断是否存在
           while(strs[i].indexOf(prefix,0)!=0)
           {   //当prefix为空的时候，就退出
               if(prefix.length()-1<=0) {
                  prefix="";
                   return "";
               }
                   
               else 
                   prefix=prefix.substring(0,prefix.length()-1);
           }       //更新前缀
       }
      return prefix;
   }
}