求字符串集合中的最长公共前缀(java递归和非递归实现)

需求:java代码实现求一个字符串集合中的最长公共前缀 比如一个集合有三个字符串AbcA,AbG,AbcD,求他们最长公共前缀就是Ab *方法一:*非递归,时间复杂度为o(n)

package com.demo.test; import java.util.ArrayList; import java.util.List; /** * 需求:java代码实现. * 一个集合有三个字符串AbcA,AbG,AbcD,求他们最长公共前缀就是Ab */ public class Test1 { public static void main(String[] args) { //1.构造原始数据 List<String> list = new ArrayList<String>(); list.add("AbcA"); list.add("AbG"); list.add("AbcD"); /** * 2.第一次假设最长公共前缀为1,去判断是否所有字符串前缀都是该字符,如果满足继续下一步 * 第二次最长公共前缀为2,去判断是否相同,如果满足继续下一步 * 一直循环,直到不满足条件为止 */ //2.1定义保存最长公共前缀的变量 String maxPublicPrefix = ""; //2.2找到最短字符串长度 int minLength = list.get(0).length(); for (int i = 0; i < list.size(); i++) { // if (list.get(i).length() < minLength) { // minLength = list.get(i).length(); // } minLength=Math.min(list.get(i).length(),minLength); } //2.3开始循环 f1: for (int i = 0; i < minLength; i++) { //假设取第一个字符串的前i个字符作为前缀 int supposePrefixLength = i; String supposePrefix = list.get(0).substring(0,supposePrefixLength+1); //那假设的前缀去原集合判断是否每个元素都有该前缀 for (int j = 0; j < list.size(); j++) { //如果有不同,结束外层循环,最长公共前缀就是上一次的结果 if (!supposePrefix.equals(list.get(j).substring(0,supposePrefixLength+1))) { break f1; } } //更新最长公共前缀 maxPublicPrefix=supposePrefix; } System.out.println("最长公共前缀为:" + maxPublicPrefix); } }

*方法二:*递归.每次对半寻找.时间复杂度为o(n/2) 分析原理图如下

package com.demo.test; import java.util.ArrayList; import java.util.List; /** * 需求:java代码实现. * 一个集合有三个字符串AbcA,AbG,AbcD,求他们最长公共前缀就是Ab */ public class Test2 { public static void main(String[] args) { //1.构造原始数据 List<String> list = new ArrayList<String>(); list.add("AbcdE"); list.add("AbcdAy"); list.add("AbcdAmmm"); //2找到最短字符串长度 int minLength = list.get(0).length(); for (int i = 0; i < list.size(); i++) { if (list.get(i).length() < minLength) { minLength = list.get(i).length(); } } //3开始循环递归循环找 //问题本质就是找索引 int low = 0; int high = minLength - 1; String lastPrefix = ""; String maxPublicPrefix = m1(low, high, lastPrefix, list); System.out.println("最长公共前缀为:"+maxPublicPrefix); } public static String m1(int low, int high, String lastPrefix, List<String> list) { if (low <= high) { int half = (low + high) / 2; String supposePrefix = list.get(0).substring(0, half + 1); //2.判断是否都相同(实际上a.和b.只能走其一) for (int i = 0; i < list.size(); i++) { if (!supposePrefix.equals(list.get(i).substring(0, half + 1))) {//有不同 //a.说明前缀在(low,half-1),不跟新前缀 lastPrefix = m1(low, half - 1, lastPrefix, list); return lastPrefix; } } //b.能到这里代表前缀为(half+1,high) //更新假设前缀 lastPrefix = m1(half + 1, high, supposePrefix, list); } return lastPrefix; } }