手提电脑做网站服务器,京津冀协同发展规划图,wordpress小清新主题图片,学校专业建设规划14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀#xff0c;返回空字符串 “”。 示例 1#xff1a; 输入#xff1a;strs [“flower”,“flow”,“flight”] 输出#xff1a;“fl” 示例 2#xff1a; 输入#xff1a;strs [“d… 14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 “”。 示例 1 输入strs [“flower”,“flow”,“flight”] 输出“fl” 示例 2 输入strs [“dog”,“racecar”,“car”] 输出“” 解释输入不存在公共前缀。 提示 1 strs.length 200 0 strs[i].length 200 strs[i] 仅由小写英文字母组成 最容易想到的思路就是先默认第一个字符串为结果 res然后遍历剩下的字符串不断根据 res 以及 str 的比较得到新的 res这样就相当于比较了所有字符串最终 res 就是公共前缀 public String longestCommonPrefix(String[] strs) {if(strs.length 0)return ;String res strs[0];for(int i 1; i strs.length; i){res getPre(res, strs[i]);if(.equals(res))break;}return res;}public String getPre(String s1, String s2){int min Math.min(s1.length(), s2.length());int i 0;while(i min s1.charAt(i) s2.charAt(i)){i;}return s1.substring(0, i);}既然有横向的那么纵向的也比较容易想到取任意一个字符串为例从第一位开始比较所有字符串某一位是否等于该字符的这一位需要注意的是不仅当遇到不同字符时需要返回当某个字符串已经被比较完也应该返回 public String longestCommonPrefix(String[] strs) {if(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){return strs[0].substring(0, i);}}}// 理论上来说返回什么都可以因为上面的情况已经包含了比较完的情况// 但是 strs 只有一个字符串时就不会进入比较// 所以需要返回 strs[0]return strs[0];}分治由于不管怎么样最终每个字符都会被比较比如第一种解法就是不断更新两个字符串比较后的结果那么其实分治也可以不过同时比较两组字符串而已 public String longestCommonPrefix(String[] strs) {if(strs.length 0)return ;return longestCommonPrefix(strs, 0, strs.length - 1);}// 分治public String longestCommonPrefix(String[] strs, int start, int end) {if(start end)return strs[start];int mid start (end - start) / 2;String left longestCommonPrefix(strs, start, mid);String right longestCommonPrefix(strs, mid 1, end);return commonPrefix(left, right);}// 获取两个字符串的公共前缀public String commonPrefix(String lcpLeft, String lcpRight) {int minLength Math.min(lcpLeft.length(), lcpRight.length()); for (int i 0; i minLength; i) {if (lcpLeft.charAt(i) ! lcpRight.charAt(i)) {return lcpLeft.substring(0, i);}}return lcpLeft.substring(0, minLength);}二分法由于最终公共前缀的长度不会大于最短字符串长度 min 那么可以在解法 2 的基础上使用二分法从 left 0 right min 开始得到最终公共前缀的长度 public String longestCommonPrefix(String[] strs) {if(strs.length 0)return ;int min Integer.MAX_VALUE;for (String str : strs) {min Math.min(min, str.length());}int left 0, right min;while(left right){int mid left (right - left 1) / 2;if(isCommonPrefix(strs, mid))left mid;else right mid - 1;}return strs[0].substring(0, left);}// 判断 length 是否为公共前缀public boolean isCommonPrefix(String[] strs, int length) { for (int i 0; i length; i) {char c strs[0].charAt(i);for(int j 1; j strs.length; j){if(strs[j].charAt(i) ! c)return false;}}return true;}
