leetcode-14-最长公共前缀

问题：

解：

请注意，该问题是查找最长公共前缀

一、水平扫描法

package com.example.demo;

public class Test14 {

    /**
     * 查找字符串数组中最长的公共**前缀**
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        //水平扫描法
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            // 因为查找的各个字符串的前缀，所以A字符串在B字符串中的开头，不是开头的话，prefix--，重新查询，制动为空时结束
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        Test14 t = new Test14();
        String[] strings = {"abcd", "abc", "ab"};
        String s = t.longestCommonPrefix(strings);
        System.out.println(s);

    }
}

二、分支法

package com.example.demo;

public class Test14 {

    /**
     * 查找字符串数组中最长的公共**前缀**
     *
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        //分治法
        if (strs == null || strs.length == 0) {
            return "";
        }
        return longestCommonPrefix1(strs, 0, strs.length - 1);
    }

    /**
     * 递归、分治
     *
     * @param strs
     * @param left
     * @param right
     * @return
     */
    private String longestCommonPrefix1(String[] strs, int left, int right) {
        // 递归终止条件
        if (left == right) {// 递归的终止条件要选择好
            return strs[left];
        } else {
            int mid = (left + right) / 2;
            // 递归的思想（不要深入想递归内部，只要在宏观上认为，该递归返回的字符串就是left到mid之间的最长公共前缀）
            String lcpLeft = longestCommonPrefix1(strs, left, mid);
            String lcpRight = longestCommonPrefix1(strs, mid + 1, right);
            //将返回的左右两个最长公共子串进行比较，获取最终的最长公共前缀
            return comparePreFix(lcpLeft, lcpRight);
        }
    }

    /**
     * 比较两个字符串中的最长前缀
     *
     * @param lcpLeft
     * @param lcpRight
     * @return
     */
    private String comparePreFix(String lcpLeft, String lcpRight) {
        int len = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < len; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, len);
    }


    public static void main(String[] args) {
        Test14 t = new Test14();
        String[] strings = {"abcd", "abc", "ab"};
        String s = t.longestCommonPrefix1(strings);
        System.out.println(s);

    }
}