烟台建网站公司哪家好,网站建设和app哪个好,wordpress 调用单页面,网站编程好学吗【问题描述】[中等]
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀#xff0c;返回空字符串 。示例 1:输入: [flower,flow,flight]
输出: fl
示例 2:输入: [dog,raceca…【问题描述】[中等]
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串 。示例 1:输入: [flower,flow,flight]
输出: fl
示例 2:输入: [dog,racecar,car]
输出:
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
【解答思路】
1. 横向扫描 时间复杂度O(N^2) 空间复杂度O(1)
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);}
}
2. 纵向扫描 时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}int length strs[0].length();int count strs.length;for (int i 0; i length; i) {char c strs[0].charAt(i);for (int j 1; j count; j) {if (i strs[j].length() || strs[j].charAt(i) ! c) {return strs[0].substring(0, i);}}}return strs[0];}
}public String longestCommonPrefix(String[] strs) {if (strs.length 0) return ;for(int i 0;istrs[0].length();i){for(int j1 ; jstrs.length;j){if(i strs[j].length() || strs[j].charAt(i)!strs[0].charAt(i)){return strs[0].substring(0,i);}}}return strs[0];}2. 二分法 时间复杂度O(mnlogm) 空间复杂度O(1)
class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}int minLength Integer.MAX_VALUE;for (String str : strs) {minLength Math.min(minLength, str.length());}int low 0, high minLength;while (low high) {int mid (high - low 1) / 2 low;if (isCommonPrefix(strs, mid)) {low mid;} else {high mid - 1;}}return strs[0].substring(0, low);}public boolean isCommonPrefix(String[] strs, int length) {String str0 strs[0].substring(0, length);int count strs.length;for (int i 1; i count; i) {String str strs[i];for (int j 0; j length; j) {if (str0.charAt(j) ! str.charAt(j)) {return false;}}}return true;}
}
4. 分治 复杂度
class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}int minLength Integer.MAX_VALUE;for (String str : strs) {minLength Math.min(minLength, str.length());}int low 0, high minLength;while (low high) {int mid (high - low 1) / 2 low;if (isCommonPrefix(strs, mid)) {low mid;} else {high mid - 1;}}return strs[0].substring(0, low);}public boolean isCommonPrefix(String[] strs, int length) {String str0 strs[0].substring(0, length);int count strs.length;for (int i 1; i count; i) {String str strs[i];for (int j 0; j length; j) {if (str0.charAt(j) ! str.charAt(j)) {return false;}}}return true;}
}
【总结】
1.纵横交错 二分分治
2. 字符串/数组题目遍历 暴力再优化 转载链接https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
