首页 > 代码库 > 14. Longest Common Prefix

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

这个问题是关于如何寻找字符串数组的公共前缀的,从第一个字母开始,只要共有的都要输出。

思路:

  1.首先,如何得到字符串共有前缀,既然共有,那么很容易先想到最短字符串。

  2.最短字符串和其余进行比较,这样就省下了大于最短字符串长度的比较。

  3.关于字符串的操作,length和null是很必要的判断输入操作,千万别忘记!

  4.关于代码的解释在下面很详尽,以供参考。

public class Solution {
    public String longestCommonPrefix(String[] strs) {//返回的是字符串类型
         if(strs==null||strs.length==0)//只要是关于字符串的代码,判空和判断长度是否为0都是必须的。
             return "";
         if(strs.length==1)//特例,如果数组长度为1,并没有办法比较,所以直接返回。
             return strs[0];
         for(int i=0;i<strs.length;i++)//这个循环是用来判断数组内的字符串是否为空或者长度为0,一旦发生,立即返回空。
         {
             if(strs[i].length()==0||strs[i]==null)
                 return"";
         }         
         int length=strs[0].length();//上面所有特例排除之后,就是正式的比较,选择了。
         int shortest=0;//表示数组中最短字符串的索引
         for(int i=1;i<strs.length;i++)//从第一个字符串开始进行比较,得到整个数组中最短的字符串长度
         {
             if(strs[i].length()<length){
                 length=strs[i].length();
                 shortest=i;
             }
         }
         for(int i=0;i<length;i++)//开始判断,最短字符串长度中有多少是共有的
         {
             char x=strs[shortest].charAt(i);
             {
                 for(int j=0;j<strs.length;j++)
                 {
                     if(strs[j].charAt(0)!=strs[shortest].charAt(0))//这也是一个特例,在比较数组中的字符串长度为1时,如果有任何两者不相等,即可返回空。
                         return "";
                     if(strs[j].charAt(i)!=x)//这个表示输出不相等之前的所有公共字符前缀
                         return strs[shortest].substring(0, i);//注意只能返回0-i-1,并不包括i。这个也就是为什么长度为1是特例了。
                 }
             }
         }
         return strs[shortest];    //如果全部都能比较完且相等,那么返回的是数组中的最短字符串本身
    }
}

方法2:这个是借鉴了一下别的思路

  1.判空很必要

  2.直接从第一个字符开始,寻找共有的字符串,如果找不到,缩小字符串长度

  3.利用string。indexof(obj)如果能找到那么返回第一个位置也就是0.

public class Solution {
    public String longestCommonPrefix(String[] strs) {
         if(strs==null||strs.length==0)
            return "";
        String pre=strs[0];//从第0个字符串开始寻找
        int i=1;
        while(i<strs.length)//全部数组遍历一遍
        {
            while(strs[i].indexOf(pre)!=0)//这里很巧妙,利用indexOf(obj)这个方法,一旦判断为0,那么找到公共前缀。
            {
                pre=pre.substring(0, pre.length()-1);//找不到的话,缩短前缀的大小,重新遍历
            }
            i++;
        }
        return pre;//最终返回找到的共有前缀即可
    }
}

第二种方法明显比第一种好多了,第一种太麻烦,因为自己刚开始学string,对很多操作都不熟悉,以后还是要多了解string的方法,这样能高效的完成程序,就当第一种是训练一下思维,第二种是学习得到升华吧,一步一步,慢慢前进!

 

14. Longest Common Prefix