最长公共前缀-java

谁借莪１个温暖的怀抱￠ 2022-10-08 15:18 169阅读 0赞

package com.leetcode.insist;
    
    import java.util.*;
    
    /**
     * 寻找最长公共前缀
     */
    public class LongestPublicPrefix {
        public String longestCommonPrefix(String[] strs) {
            if(strs.length==0){
                return "";
            }
            //先找出最短的,防止越界
            List<String> list = Arrays.asList(strs);
            String minValue = getMinValue(list);
            System.out.println(minValue+"==min");
            String t2 = "";
            for(int i=0;i<minValue.length();i++){
                t2 += minValue.charAt(i);
                for(int j=0;j<strs.length;j++){
                    System.out.println(strs[j].substring(0, i+1)+"=========");
                    boolean flag = t2.equals(strs[j].substring(0, i+1)); //越界
                    if(i==0){
                        flag = t2.equals(strs[j].charAt(0)+"");
                    }
                    if(flag){
                        continue;
                    }else{
                        if(t2.length()>1){
                            return t2.substring(0,t2.length()-1);
                        }else{
                            return "";
                        }
                    }
                }
            }
            //只有一个元素的情况
            if(strs.length==1){
                return strs[0];
            }
            //这应该是全部相等的情况
            return minValue;
        }
        public String getMinValue( List<String> arrayList) {
            //定义一个map来存截取的数据
            HashMap<Integer,String> hashMap=new  HashMap<Integer,String>();
            for (String string : arrayList) {
                int len=string.length();
                hashMap.put(string.length(), string);
            }
            //获取所有的key值
            Set<Integer> set = hashMap.keySet();
            Object[] obj = set.toArray();
            //排序
            Arrays.sort(obj);
            //最小的Value值的变量
            String  resultValue = "";
            //根据key ,找Value
            for(Map.Entry<Integer,String> str : hashMap.entrySet()){
                if(obj[0].equals(str.getKey())){
                    resultValue = str.getValue();
                }
            }
            return resultValue ;
        }
        public static void main(String[] args) {
            String strs[] = {"c","acc","ccc"};
    //        String strs[] = {"flower","flow","flight"};
    //        String strs[] = {"ab","a"};
            String s = new LongestPublicPrefix().longestCommonPrefix(strs);
            System.out.println("s="+s);
    
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BzaGRoeA_size_16_color_FFFFFF_t_70][]

class Solution {
        public String longestCommonPrefix(String[] strs) {
            if (strs == null || strs.length == 0) {
                return "";
            }
            String prefix = strs[0];
            int count = strs.length;
            for (int i = 1; i < count; i++) {
                prefix = longestCommonPrefix(prefix, strs[i]);
                if (prefix.length() == 0) {
                    break;
                }
            }
            return prefix;
        }
    
        public String longestCommonPrefix(String str1, String str2) {
            int length = Math.min(str1.length(), str2.length());
            int index = 0;
            while (index < length && str1.charAt(index) == str2.charAt(index)) {
                index++;
            }
            return str1.substring(0, index);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BzaGRoeA_size_16_color_FFFFFF_t_70]: /images/20221005/04d3138da94348409df35fff1b55391a.png