欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode题解(Java):14-最长公共前缀

程序员文章站 2022-03-22 23:50:20
14. 最长公共前缀https://leetcode-cn.com/problems/longest-common-prefix/解法一:横向比较class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < s...

14. 最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

解法一:横向比较

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
        	int k = 0;
            String candidate = strs[i];
            int minLength = Math.min(prefix.length(), candidate.length());
            while (k < minLength && prefix.charAt(k) == candidate.charAt(k)) {
                k++;
            }
            prefix = prefix.substring(0, k);
        }
        return prefix;
    }
}

解法二:纵向比较

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        int i = 0;
        while (i < prefix.length()) {
            char ch = prefix.charAt(i);
            for (int j = 1; j < strs.length; j++) {
                String candidate = strs[j];
                if (i > candidate.length() - 1 || ch != candidate.charAt(i)) {
                    return prefix.substring(0, i);
                }
            }
            i++;
        }
        return prefix;
    }
}

解法三:分治

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        return dac(strs, 0, strs.length - 1);
    }

    public String dac(String[] strs, int lo, int hi) {
        if (lo == hi) return strs[lo];
        int mid = lo + ((hi - lo) >> 1);
        String left = dac(strs, lo, mid);
        String right = dac(strs, mid + 1, hi);
        return lcp(left, right);
    }

    public String lcp(String s1, String s2) {
        int minL = Math.min(s1.length(), s2.length());
        for (int i = 0; i < minL; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                return s1.substring(0, i);
            }
        }
        return s1.substring(0, minL);
    }
}

解法四:二分查找

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        int minLen = Integer.MAX_VALUE;
        for (String s : strs) {
            minLen = Math.min(minLen, s.length());
        }
        int lo = 0, hi = minLen - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (check(strs, lo, mid)) {// [lo, mid] is same
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return strs[0].substring(0, lo);
    }

    public boolean check(String[] strs, int lo, int hi) {
        String prefix = strs[0];
        while (lo <= hi) {
            for (int i = 1; i < strs.length; i++) {
                if (prefix.charAt(lo) != strs[i].charAt(lo)) {
                    return false;
                }
            }
            lo++;
        }
        return true;
    }
}

解法五:indexOf() || startWith()

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            // while (!strs[i].startsWith(prefix)) {
            //     prefix = prefix.substring(0, prefix.length() - 1);
            // }
            while (0 != strs[i].indexOf(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }
}

本文地址:https://blog.csdn.net/qq_29511515/article/details/107289668