【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"});      // ""
    }
}