【LeeCode】14. 最长公共前缀

【题目描述】

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ​​""​​。

​​​​https://leetcode.cn/problems/longest-common-prefix/description/​​

【示例】

【代码】官方:​​推荐​​

从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return  "";

int len = strs[0].length();
int count = strs.length;
for (int i = 0; i < len; i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < count; j++){
// 这里有一个判字符为空的场景
if (i == strs[j].length() || strs[j].charAt(i) != c){
System.out.println(strs[0].substring(0, i));
return strs[0].substring(0, i);
                }
            }
        }
return strs[0];
    }
}

【代码】官方2

思路： 依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

package com.company;
// 2023-01-02

class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return  "";

String prefix = strs[0];
int len = strs.length;
for (int i = 1; i < len; i++) {
prefix = check(prefix, strs[i]);
if (prefix.length() == 0){
break;
            }
        }
return prefix;
    }

// 2个字符串依次迭代进行判断
public String check(String s1, String s2){
// 返回最长的公共字符串
int len = Math.min(s1.length(), s2.length());
int index = 0;
while (index < len && s1.charAt(index) == s2.charAt(index)){
index++;
        }
return s1.substring(0, index);
    }

}
class Test{
public static void main(String[] args) {
new Solution().longestCommonPrefix( new String[]{"flower","flow","flight"});  // "fl"
new Solution().longestCommonPrefix( new String[]{"cir","car"});               // "c"
new Solution().longestCommonPrefix(new String[]{"dog","racecar","car"});      // ""
new Solution().longestCommonPrefix(new String[]{"reflower","flow","flight"}); // ""
new Solution().longestCommonPrefix(new String[]{"dog","racecar","car"});        // ""
new Solution().longestCommonPrefix(new String[]{""});            // ""
new Solution().longestCommonPrefix(new String[]{"a"});           // "a"
new Solution().longestCommonPrefix(new String[]{"ab", "a"});     // "a"
new Solution().longestCommonPrefix(new String[]{"",""});         // ""
    }
}

【代码】admin

这里有个关键就是，前缀, 而非公共字符串 所以需要找一个最小的不为空的字符来进行一次比较 如果第一个字符都不一样, 那就没有公共的前缀

这里很多需要判断的地方， 如果字符串数组的长度是1，则直接返回即可(无论是空字符还是单个字符串)

还要判断字符串数组中是否有空字符串, 如果有空字符串,则直接返回空即可“”

思路： 找到最小的、合法字符串, 把数组转list 然后轮训判断min的每个字符是否存在于其他字符串中

PS： 看了其他的解法, 其实依次迭代进行对比就行, 还比较简单。另也不用最小的字符进行对比, 第一个就可

package com.company;
// 2023-01-02

import java.util.*;
import java.util.stream.Collectors;

class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果只有一个字符串,则直接返回即可
if (strs.length == 1) return strs[0];
// 如果最小的字符串的长度是0, 则表示有为空的字符串, 直接返回空
String min = Arrays.stream(strs).filter(x -> x.length() >= 0).min(Comparator.comparingInt(String::length)).get();
// System.out.println("min --> " + min.length());
if (min.length() < 1) return "" ;
// 字符串数组转list
List<String> collect = Arrays.stream(strs).filter(x -> x.length() > 0).collect(Collectors.toList());

boolean flag = true;
StringBuilder sb = new StringBuilder();

for (int i = 0; i < min.length(); i++) {
for (String x : collect) {
if (x.charAt(i) != min.charAt(i)){
flag = false;
                }
            }
if (flag) {
sb.append(min.charAt(i));
            }else {
System.out.println(sb.toString());
return sb.toString();
            }
        }

System.out.println(sb.toString());
return  sb.toString();
    }
}
class Test{
public static void main(String[] args) {
new Solution().longestCommonPrefix( new String[]{"flower","flow","flight"});  // "fl"
new Solution().longestCommonPrefix( new String[]{"cir","car"});               // "c"
new Solution().longestCommonPrefix(new String[]{"dog","racecar","car"});      // ""
new Solution().longestCommonPrefix(new String[]{"reflower","flow","flight"}); // ""
new Solution().longestCommonPrefix(new String[]{"dog","racecar","car"});        // ""
new Solution().longestCommonPrefix(new String[]{""});            // ""
new Solution().longestCommonPrefix(new String[]{"a"});           // "a"
new Solution().longestCommonPrefix(new String[]{"ab", "a"});     // "a"
new Solution().longestCommonPrefix(new String[]{"",""});         // ""
    }
}

【代码】admin

思路1： 找到最小的字符, 然后判断字符c是否每个字符串都包含，但这里有个问题就是 如果类似 ”reflow”,"flow" 就会导致发现公共字符串，而并非最长公共前缀；  本例通过率  103/124

package com.company;
// 2023-01-02

import java.util.*;
import java.util.stream.Collectors;

class Solution {
public String longestCommonPrefix(String[] strs) {
String min = Arrays.stream(strs).min(Comparator.comparingInt(String::length)).get();
List<String> collect = Arrays.stream(strs).collect(Collectors.toList());
StringBuilder sb = new StringBuilder();
int index = 0;
for (int i = 0; i < min.length(); i++){
boolean flag = true;
char c = min.charAt(i);
for (String x : collect) {
if (x.indexOf(c) < 0 ){
index = -1;
flag = false;
break;
                }
            }
if (flag && index != -1)
sb.append(c);
        }
System.out.println(sb.toString());
return sb.toString();
    }
}
class Test{
public static void main(String[] args) {
new Solution().longestCommonPrefix( new String[]{"flower","flow","flight"});  // "fl"
new Solution().longestCommonPrefix( new String[]{"cir","car"});  // ""
new Solution().longestCommonPrefix(new String[]{"dog","racecar","car"});      // ""
    }
}