企业网站开发语言,冠县网站建设费用,网站建设有利于,阿里云域名查询和注册题目描述 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀#xff0c;返回空字符串 。 示例 1:输入: [flower,flow,flight]输出: fl示例 2:输入: [dog,racecar,返回空字符串 。 示例 1:输入: [flower,flow,flight]输出: fl示例 2:输入: [dog,racecar,car]输出: 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。 解决方法 横向匹配所有字符串 取出字符串数组里任意一个字符串prefix遍历其余的字符串判断prefix是否是其的前缀不是就去掉prefix最后一个字符直到prefix为空 public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0)return ;String prefix strs[0];for (int i 1; i strs.length; i) {while (strs[i].indexOf(prefix) ! 0) {prefix prefix.substring(0, prefix.length() - 1);if (prefix.isEmpty())return ;}}return prefix;} 时间复杂度O(S)其中S是所有字符串中所有字符的总和空间复杂度O(1)只使用了恒定的额外空间 二分搜索 取最短的字符串的长度minLen作为右边界right因为最长公共前缀的长度不可能大于字符串数组里最短字符串的长度判断左半部分是否是公共前缀是的话向右寻找更长的公共前缀反之向左寻找公共前缀当 左边界left 右边界right 寻找结束最长公共前缀范围就是[0, (left right) / 2) public String longestCommonPrefix2(String[] strs) {if (strs null || strs.length 0)return ;int minLen Integer.MAX_VALUE;for (String str : strs)minLen Math.min(minLen, str.length());int left 1, right minLen;while (left right) {int middle (left right) / 2;if (isCommonPrefix(strs, middle))left middle 1;elseright middle - 1;}return strs[0].substring(0, (left right) / 2);}public boolean isCommonPrefix(String[] strs, int len) {String str1 strs[0].substring(0, len);for (int i 1; i strs.length; i) {if (!strs[i].startsWith(str1))return false;}return true;} 时间复杂度O(S*log(n))其中S是所有字符串中所有字符的总和。空间复杂度O(1)。我们只使用了恒定的额外空间。 本文首发https://lierabbit.cn/2018/05/...
