算法题--最长公共前缀 [LeetCode]

题目描述

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

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

示例 1:

  输入: [“flower”,“flow”,“flight”]

  输出: “fl”

示例 2:

  输入: [“dog”,“racecar”,“car”]

  输出: “”

  解释: 输入不存在公共前缀。

说明：

  所有输入只包含小写字母 a-z 。

题解

方法一：横向扫描法

  前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。

public static String longestCommonPrefix(String[] strs) {

        if(null == strs || strs.length == 0){
            return "";
        }

        if(strs.length == 1){
            return strs[0];
        }

        String commonPrefix = strs[0];
        int commonPrefixLen;
        for(int i=1; i<strs.length; i++){
            while(strs[i].indexOf(commonPrefix) != 0){
                commonPrefixLen = commonPrefix.length() -1;
                if(commonPrefixLen == 0){
                    return "";
                }
                commonPrefix = commonPrefix.substring(0,commonPrefixLen);
            }
        }

        return commonPrefix;
    }
           

复杂度分析：

• 时间复杂度：O(n*m)。最坏情况下，输入数据为 n 个长度为 m 的相同字符串，算法会进行n*m次比较。
• 空间复杂度：O(1)。

方法二：横向扫描+二分查找法

  跟方法一相同，前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。但是在每两个字符串找公共子串时，用二分法。

public static String longestCommonPrefix2(String[] strs) {

        if(null == strs || strs.length == 0){
            return "";
        }

        if(strs.length == 1){
            return strs[0];
        }

        int high = strs[0].length();
        int low = 0;
        int middle;
        for(int i=1; i<strs.length; i++){
            while(low <= high){
                middle = (low + high)/2;
                if(strs[i].indexOf(strs[0].substring(0,middle)) == 0){
                    low = middle + 1;
                }else{
                    high = middle - 1;
                }
            }
            low = 0;
            high = Math.min(high,strs[i].length());
        }

        return strs[0].substring(0,high);

    }
           

复杂度分析：

• 时间复杂度：O( n * log(m) )。最坏情况下，输入数据为 n 个长度为 m 的相同字符串，算法会进行 n * log(m) 次比较。
• 空间复杂度：O(1)。

方法三：纵向扫描法

  从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。

代码（略）
           

复杂度分析：

• 时间复杂度：O(n*m)。最坏情况下，输入数据为 n 个长度为 m 的相同字符串，算法会进行n*m次比较。
• 空间复杂度：O(1)。

方法四：Trie字典树

  字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

  它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

public static String longestCommonPrefix3(String[] strs) {
        if(null == strs || strs.length == 0){
            return "";
        }

        if(strs.length == 1){
            return strs[0];
        }

        Trie trie = new Trie();
        for (int i = 1; i < strs.length ; i++) {
            trie.insert(strs[i]);
        }
        return trie.searchLongestPrefix(strs[0]);
    }
           

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    public String searchLongestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
                prefix.append(curLetter);
                node = node.get(curLetter);
            }
            else{
                return prefix.toString();
            }
        }
        return prefix.toString();
    }
}

class TrieNode {

    /**
     * R links to node children
     */
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    /**
     * 非空子节点的数量
     */
    private int size;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
        size++;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }

    public int getLinks() {
        return size;
    }
}
           

复杂度分析：

• 时间复杂度：最坏情况下，输入数据为 n 个长度为 m 的相同字符串，预处理过程的时间复杂度为O(n * m)，最长公共前缀查询操作的复杂度为 O(m)。
• 空间复杂度：O(n * m)， 我们需要使用额外的 n * m 空间建立字典树。

题目地址：https://leetcode-cn.com/problems/longest-common-prefix/solution/