letcode--最长公共前缀

题目

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

解法一：暴力解法

思路

 （1）找到字符串数组中字符串最短的长度（2）循环截取每个字符串放到数组中，循环（1）获取的最短长度，在对每个list去重（3）如果list去完重以后的长度为1，则说明是公共字符串，否者退出循环，返回

代码

    /*** 解法一：* （1）找到字符串数组中字符串最短的长度* （2）循环截取每个字符串放到数组中，循环（1）获取的最短长度，在对每个list去重* （3）如果list去完重以后的长度为1，则说明是公共字符串，否者退出循环，返回* @param strs* @return*/public static  String longestCommonPrefix_1(String[] strs) {
    if(strs.length == 0){
    return "";}//获取最短长度int min_length = strs[0].length();for (int i = 1; i < strs.length; i++) {
    if(strs[i].length() < min_length){
    min_length = strs[i].length();}}//计算公共数组List ll = new ArrayList();for(int i = 0;i<min_length;i++){
    List ss = new ArrayList<>();for(int j = 0;j < strs.length;j++) {
    String str = strs[j];ss.add(str.charAt(i));}//java8新特性去重, ss--> ['f','f','f'] --> ['f'] -->公共前缀ll.add(ss.stream().distinct().collect(Collectors.toList()));}//拼接公共字符串String same_str= "";for(int i = 0;i < ll.size();i++){
    if(((List)ll.get(i)).size() == 1){
    same_str += ((List)ll.get(i)).get(0);}else{
    break;}}return same_str;}

结果

解法二：横向扫描

思路

 （1）初始化same_str为字符串数组的第一个字符串（2）从下标1开始依次遍历字符串数组中的字符串，每次遍历和最长公共前缀same_str比较，找出他们之间的公共前缀放置到temporary_str中， 如果比较不相等把零时字符串赋值给same_str，退出循环（3）遍历完same_str为最长的公共字符串

代码

  /*** 解法二：* 横向扫描* （1）初始化same_str为字符串数组的第一个字符串* （2）从下标1开始依次遍历字符串数组中的字符串，每次遍历和最长公共前缀same_str比较，找出他们之间的公共前缀放置到temporary_str中，* 如果比较不相等把零时字符串赋值给same_str，退出循环* （3）遍历完same_str为最长的公共字符串* @param strs* @return*/public static  String longestCommonPrefix_2(String[] strs){
    if(strs.length == 0){
    return "";}//默认初始的最长公共前缀为字符串数组的第一个String same_str = strs[0];for (int i = 1; i < strs.length ; i++) {
    int min_length = same_str.length() < strs[i].length() ? same_str.length():strs[i].length();//定义零时字符串，放置公共前缀String temporary_str = "";for (int j = 0; j < min_length ; j++) {
    if(same_str.charAt(j) == strs[i].charAt(j)){
    temporary_str += same_str.charAt(j);}else{
    break;}}same_str = temporary_str;}return same_str;}

结果

解法三：纵向扫描

思路

 （1）获取字符串数组中最短字符串的长度，这个长度就是纵向扫描的次数，及i列（2）纵向扫描第一轮：遍历字符串数组，两两的字符串的第i列比较，如果相等赋值给ch,一轮下来都相等，则是公共字符串，如果不相等，返回当前的最长公共前缀

代码

    /***解法三：* 纵向扫描* (1)获取字符串数组中最短字符串的长度，这个长度就是纵向扫描的次数，及i列*（2）纵向扫描第一轮：遍历字符串数组，两两的字符串的第i列比较，如果相等赋值给ch,一轮下来都相等，则是公共字符串* 如果不相等，返回当前的最长公共前缀* @param strs* @return*/public static  String longestCommonPrefix_3(String[] strs){
    if(strs.length == 0){
    return "";}//如果数组只有一个字符串if(strs.length == 1){
    return strs[0];}//获取最短长度int min_length = strs[0].length();for (int i = 1; i < strs.length; i++) {
    if(strs[i].length() < min_length){
    min_length = strs[i].length();}}String same_str = "";//纵向扫描for (int i = 0; i < min_length ; i++) {
    char ch = ' ';for (int j = 0; j < strs.length - 1; j++) {
    //第j行第i列，两两比较if(strs[j].charAt(i) == strs[j+1].charAt(i)){
    ch = strs[j].charAt(i);}else{
    //如果纵向扫描有不相等的，就返回当前的最长公共前缀return same_str;}}same_str += ch;}return same_str;}

结果

解法四：分治法

思路

 （1）把问题分解为两个子问题，先求出两个子问题的最长公共前缀（2）最后求把两个子问题得到的最长公共前缀即为最长公共前缀

代码

    /*** 解法4：* 分治思想* （1）把问题分解为两个子问题，先求出两个子问题的最长公共前缀* （2）最后求把两个子问题得到的最长公共前缀即为最长公共前缀* @param strs* @return*/public static  String longestCommonPrefix_4(String[] strs){
    if(strs == null || strs.length == 0){
    return "";}else{
    return longestCommonPrefix_4(strs,0,strs.length - 1);}}public static String longestCommonPrefix_4(String[] strs,int start,int end){
    if(start == end){
    return strs[start];}else{
    //计算midint mid = (end - start)/2 + start;//递归调用String left = longestCommonPrefix_4(strs,start,mid);String right = longestCommonPrefix_4(strs,mid+1,end);return commonPrefix_4(left,right);}}//取两个字符串公共前缀public static String commonPrefix_4(String left,String right){
    int min_length = Math.min(left.length(),right.length());for (int i = 0; i < min_length; i++) {
    if(left.charAt(i) != right.charAt(i)){
    return left.substring(0,i);}}return left.substring(0,min_length);}

结果

总结

要善于发散思维，学会用不同思维方式想问题，从而让问题越来越简单化。