编写一个函数来查找字符串数组中的最长公共前缀
https://leetcode-cn.com/problems/longest-common-prefix/
示例1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
Java解法
思路：
简单思路：两两取出公共串，做为新串与下个字符串比较，有公共继续知道比较完成，输出；若无则表示没有公共串
犯二：这里做拆分求两个字符串的公共前缀做成了求公共子串public static String getCommon(String s1, String s2) { int i = 0; List<Character> list = new ArrayList<>(); String result = ""; while (i<s1.length()&&i<s2.length()){ if (s1.charAt(i)==s2.charAt(i)) { list.add(s1.charAt(i)); }else { String temp = ""; for (Character character : list) { temp+=character; } list.clear(); result = result.length()>=temp.length()?result:temp; } i++; } String temp = ""; for (Character character : list) { temp+=character; } result = result.length()>=temp.length()?result:temp; return result; }
package sj.shimmer.algorithm;
/**
* Created by SJ on 2021/2/2.
*/
class D9 {
public static void main(String[] args) {
System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"}));
System.out.println(longestCommonPrefix(new String[]{"cir","car"}));
System.out.println(longestCommonPrefix(new String[]{"flower","fkow"}));
}
public static String longestCommonPrefix(String[] strs) {
if (strs==null||strs.length==0) {
return "";
}
String result = strs[0];
for (int i = 1; i < strs.length; i++) {
String common = getCommonPre(result, strs[i]);
if (common!=null&&common!="") {
result = common;
}else {
return "";
}
}
return result;
}
public static String getCommonPre(String s1, String s2) {
int i = 0;
String result = "";
while (i<s1.length()&&i<s2.length()){
if (s1.charAt(i)==s2.charAt(i)) {
result+=s1.charAt(i);
}else {
return result;
}
i++;
}
return result;
}
}
image
官方解
-
横向扫描
上方同样的思路,但官方的求公共前缀方法明显更好，计算位置再剪切，提高了大量效率
public String getCommonPre(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); > } > ``` > > - 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
- 空间复杂度： O(1)。使用的额外空间复杂度为常数
-
纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。z
- 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
- 空间复杂度： O(1)。使用的额外空间复杂度为常数
-
分治
分支算法中的将大问题拆分子问题，由子问题的结果最终得出大问题的结果
在这里：
- 多个字符串的公共串分解为，两两 得公共串，
- 新的公共串列 又分解为，两两得公共串
- 类似于对横向扫描的优化，横向的循环对比，这里可以快速对比（类似排序算法中归并排序，还可以多路归并）
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。
- 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 log n，每层需要 m 的空间存储返回结果# Day9 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀
https://leetcode-cn.com/problems/longest-common-prefix/
示例1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
Java解法
思路：
简单思路：两两取出公共串，做为新串与下个字符串比较，有公共继续知道比较完成，输出；若无则表示没有公共串
犯二：这里做拆分求两个字符串的公共前缀做成了求公共子串public static String getCommon(String s1, String s2) { int i = 0; List<Character> list = new ArrayList<>(); String result = ""; while (i<s1.length()&&i<s2.length()){ if (s1.charAt(i)==s2.charAt(i)) { list.add(s1.charAt(i)); }else { String temp = ""; for (Character character : list) { temp+=character; } list.clear(); result = result.length()>=temp.length()?result:temp; } i++; } String temp = ""; for (Character character : list) { temp+=character; } result = result.length()>=temp.length()?result:temp; return result; }
package sj.shimmer.algorithm;
/**
* Created by SJ on 2021/2/2.
*/
class D9 {
public static void main(String[] args) {
System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"}));
System.out.println(longestCommonPrefix(new String[]{"cir","car"}));
System.out.println(longestCommonPrefix(new String[]{"flower","fkow"}));
}
public static String longestCommonPrefix(String[] strs) {
if (strs==null||strs.length==0) {
return "";
}
String result = strs[0];
for (int i = 1; i < strs.length; i++) {
String common = getCommonPre(result, strs[i]);
if (common!=null&&common!="") {
result = common;
}else {
return "";
}
}
return result;
}
public static String getCommonPre(String s1, String s2) {
int i = 0;
String result = "";
while (i<s1.length()&&i<s2.length()){
if (s1.charAt(i)==s2.charAt(i)) {
result+=s1.charAt(i);
}else {
return result;
}
i++;
}
return result;
}
}
官方解
-
横向扫描
上方同样的思路,但官方的求公共前缀方法明显更好，计算位置再剪切，提高了大量效率
public String getCommonPre(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); > } > ``` > > - 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
- 空间复杂度： O(1)。使用的额外空间复杂度为常数
-
纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。z
- 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
- 空间复杂度： O(1)。使用的额外空间复杂度为常数
-
分治
分支算法中的将大问题拆分子问题，由子问题的结果最终得出大问题的结果
在这里：
- 多个字符串的公共串分解为，两两 得公共串，
- 新的公共串列 又分解为，两两得公共串
- 类似于对横向扫描的优化，横向的循环对比，这里可以快速对比（类似排序算法中归并排序，还可以多路归并）
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。
- 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 log n，每层需要 m 的空间存储返回结果
