博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode -- Longest Common Prefix
阅读量:5834 次
发布时间:2019-06-18

本文共 4347 字,大约阅读时间需要 14 分钟。

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

方法1:BF, 首先计算两个字符串的prefix,每次用这个prefix与下一个字符串生成新的prefix

效果较差,大数据集直接挂了,代码可读性太差-_-!

1 public String longestCommonPrefix(String[] strs) { 2         // Start typing your Java solution below 3         // DO NOT write main() function 4         String commonPre = null; 5         int commonPreLength = 0; 6         if(strs.length == 0){ 7             return ""; 8         } else if(strs.length == 1){ 9             return strs[0];10         } else {11             String a = strs[0];12             String b = strs[1];13             String abPrefix = findCommonPrefix(a, b);14             int abPrefixSize = abPrefix.length();15             16             int strsSize = strs.length - 2;17             for(int i = 0; i < strsSize; i++){18                 String tmp = strs[i + 2];19                 int tmpLength = tmp.length();20                 if(tmpLength >= abPrefixSize && tmp.substring(0, abPrefixSize).equals(abPrefix))21                     continue;22                 else if(tmpLength >= abPrefixSize && !tmp.substring(0, abPrefixSize).equals(abPrefix)){23                     abPrefix = abPrefix.substring(0, abPrefixSize - 1);24                     abPrefixSize = abPrefix.length();25                     i--;26                     continue;27                 }    28                 if(tmpLength < abPrefixSize){29                     abPrefix = abPrefix.substring(0, tmpLength);30                     abPrefixSize = abPrefix.length();31                     i--;32                     continue;33                 }34                 35                 36                 37             }38             return abPrefix;39         }40     }41     42     public String findCommonPrefix(String a, String b){43         int length = Math.min(a.length(), b.length());44         int i;45         for(i = 0; i < length; i++){46             if(a.charAt(i) != b.charAt(i)){47                 break;48             }49         }50         return a.substring(0, i);51     }

 refactor code, 但BF的时间复杂度仍然有O(n^2)

1 public String longestCommonPrefix(String[] strs) { 2         String compare = ""; 3         if(strs.length == 0) 4             return compare; 5          6         compare = strs[0]; 7         for(int i = 1; i < strs.length; i++){ 8             int j = 0; 9             while(j < compare.length() && j < strs[i].length()){10                 if(compare.charAt(j) != strs[i].charAt(j)){11                     break;12                 }13                 j++;14             }15             compare = strs[i].substring(0, j);16         }17         return compare;18     }

 方法二:依次比较每个字符串的相应位置的字符,直到遇到不匹配项。可以减少不必要的比较

1    public String longestCommonPrefix(String[] strs) { 2         String compare = ""; 3         if(strs.length == 0) 4             return compare; 5          6         int k = 0; 7         while(true){ 8             if(k == strs[0].length()) 9                 break;10             char p = strs[0].charAt(k); 11             int i;12             for(i = 1; i < strs.length; i++){13                 if(k == strs[i].length())14                     break;15                 16                 if(p != strs[i].charAt(k)){17                     break;18                 }19             }20             21             if(i != strs.length)22                 break;23             24             compare += p;25             k++;26         }27         28         return compare;29     }

 refactor code

1 public String longestCommonPrefix(String[] strs) { 2          String compare = ""; 3          if(strs.length == 0) 4              return compare; 5           6          int k = 0; 7          while(true){ 8              char p = ' ';  9              int i;10              for(i = 0; i < strs.length; i++){11                  12                  if(k == strs[i].length())13                      break;14                      15                 if(i == 0){16                     p = strs[i].charAt(k);17                 }18                  19                  if(p != strs[i].charAt(k)){20                      break;21                  }22              }23              24              if(i != strs.length)25                  break;26              27              compare += p;28              k++;29          }30          31          return compare;32      }

 

 

转载地址:http://zwucx.baihongyu.com/

你可能感兴趣的文章
兰州青年志愿者“中西合璧”玩快闪 温暖旅客回家路
查看>>
计划10年建10万廉价屋 新西兰政府:比想象中难
查看>>
甘肃发首版《3D打印职业教育教材》:校企合作育专才
查看>>
李娜入选国际网球名人堂 成亚洲第一人
查看>>
为找好心人抚养孩子 浙江一离婚父亲将幼童丢弃公园
查看>>
晚婚晚育 近20年巴西35岁以上孕妇增加65%
查看>>
读书:为了那个美妙的咔哒声
查看>>
jsp改造之sitemesh注意事项
查看>>
SpringBoot-Shiro使用
查看>>
iOS 9.0之后NSString encode方法替换
查看>>
解决 ThinkPHP5 无法接收 客户端 Post 传递的 Json 参数
查看>>
ASMFD (ASM Filter Driver) Support on OS Platforms (Certification Matrix). (文档 ID 2034681.1)
查看>>
CRM Transaction处理中的权限控制
查看>>
[转]linux创建链接文件的两种方法
查看>>
python ipaddress模块使用
查看>>
文件权限
查看>>
busybox里的僵尸进程为何那么多
查看>>
python debug
查看>>
java 连接数据库之一个完整的函数
查看>>
mysql脚本
查看>>