字符串数组的共同最长前缀

/**
 * Created by chris on 2014/11/17.
 * 找一个字符串数组中共同的最长前缀字符串
 * e.g. abc,ab,a共同最长前缀是a
 * 一层一层,横向扫描获取最长字符串
 * 或者,纵向由左到有扫描,逐渐减少最长前缀
 */
public class CommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        int len = 0;
        StringBuilder sb = new StringBuilder();

        len = strs[0].length();
        for (int i = 1; i < strs.length; i++) {// find the min length
            if (strs[i].length() < len)
                len = strs[i].length();
        }
        if (len == 0) return "";

        for (int i = 0; i < len; i++) {
            for (int j = 1; j < strs.length; j++) {
                if (strs[0].charAt(i) != strs[j].charAt(i)){
                    return sb.toString();
                }else if(j + 1 >= strs.length){
                    sb.append(strs[j].charAt(i));
                }else{
                    continue;
                }
            }
        }
        return sb.toString();
    }

/**
 * 纵向扫描,由左到右,逐渐减小最长前缀
 * */
    public String longestCommonPrefix2(String[] strs) {
        if(strs.length==0) return "";
        String str0 = strs[0];
        if(str0.length()==0) return "";
        int rightMostIndex = str0.length()-1;
        for(int k=1;k<strs.length;k++){
            for(int i=0;i<=rightMostIndex;i++){
                if((i>strs[k].length()-1)||strs[k].charAt(i)!=str0.charAt(i))
                    rightMostIndex=i-1;
            }
        }
        return rightMostIndex>=0?str0.substring(0,rightMostIndex+1):"";
    }
}
Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据