【算法】【线性表】最长公共前缀

1  题目

给k个字符串，求出他们的最长公共前缀(LCP)

样例 1：

输入：

k个字符串 = ["ABCD", "ABEF", "ACEF"]

输出：

"A"

解释：公共最长前缀是"A".

样例 2：

输入：

k个字符串 = ["ABCDEFG", "ABCEFG", "ABCEFA"]

输出：

"ABC"

解释：公共最长前缀是"ABC".

2  解答

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    public String longestCommonPrefix(String[] strs) {
        // write your code here
        // 1、数组为空或者长度为0 直接返回
        if (strs == null || strs.length == 0) {
            return "";
        }
        Set<String> strSets = new HashSet<>(strs.length);
        // 先把第一个元素拆开放里边
        String one = strs[0];
        String res =  one;
        for (int i = 0; i < one.length(); i++) {
            strSets.add(one.substring(0, one.length()-i));
        }
        // 从第二个开始遍历，判断每个的子序列是否存在
        for (int i = 1; i < strs.length; i++) {
            String str = strs[i];
            int j = str.length();
            String substring = "";
            // 长度从大到小看每个子序列是否存在
            while (j >= 0) {
                substring = str.substring(0, j);
                // 存在就跳出循环
                if (strSets.contains(substring)) {
                    break;
                }
                j--;
            }
            // 如果长度比当前小，返回结果则指向当前结果
            if (substring.length() < res.length()) {
                res = substring;
            }
        }
        return res;
    }
}

加油。