14. Longest Common Prefix

    xiaoxiao2021-03-25  119

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

    (1)求最长公共前缀,可以把它和动态规划的最长公共子序列放到一起思考,s1,s2,,,sn的公共前缀一定是s1,s2,s3,s4公共前缀的一部分,一定是s1,s2的公共前缀的一部分. s1和s2的公共前缀:s1:helloworld 如果s2前缀s1则s1为公共前缀,否则s1长度缩短,再重复判断。

    public String longestCommonPrefix(String[] strs){ if(strs.length==0) return ""; int length=strs.length; String com=strs[0]; for(int i=1;i<length;i++){ while(strs[i].indexOf(com)!=0){ com=com.substring(0, com.length()-1); // System.out.println(com); if(com.isEmpty()) return ""; } } System.out.println(com); return com; } (2)纵向考虑:如果按照方法1考虑,时间复杂度为O(S ),S为所有字符和,如果当s1很长sn很短时,不够高效,所以纵向考虑。纵向考虑注意要先判断串的长度大小(避免越界 ),再判断两串所选字符是否相同;

    public String longestCommonPrefix2(String[] strs){ if(strs==null||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()||strs[j].charAt(i)!=c){ //注意先判断i 和串长大小,再去判断两个字符是否相等 return strs[0].substring(0,i); } } } return strs[0]; }

    转载请注明原文地址: https://ju.6miu.com/read-14380.html

    最新回复(0)