1. 最长公共前缀

难度 简单

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

一开始的思路很简单，就是单纯的遍历所有字符串，两两比较，不断更新最长公共前缀的下标index，可是这样一来时间复杂度就很高为 O(N（数组中所有字符串的总长度）)

public String longestCommonPrefix1(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        String max_Common = strs[0]; //初始最长为第一个元素
        for(int i =1;i <strs.length;i++){ //然后max_common不断和剩下的进行比较
            int index = -1;
            for(int j = 0;j < strs[i].length() && j < max_Common.length();j++){
                if(strs[i].charAt(j) != max_Common.charAt(j)){
                    break;
                }
                index = j; 
            }
            if(index == -1){ //没有公共部分
                return "";//直接返回就好了
            }else{
                max_Common = max_Common.substring(0,index); //这里不断更新max_common！！！
            }
        }
        return max_Common;
    }

这推荐一个评论的思路

• 通过字符串中字典序的比较，找到字典序最大和最小的两个字符串，这两者的公共前缀就是最长的公共前缀！！！时间复杂度为O(n + min(max.length,min.length))
• 即也可以通过将数组排序，找到首尾这两个字典序最小和最大的字符串，看看两者的差异即可！！这样时间复杂比较高，为O(n * log(n) + min(max.length,min.length))

两者的原理是一样的，都是为了找到字典序最大和最小的字符串！（关于时间复杂度这里忽略字典序比较上的开销）

代码如下

public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        Arrays.sort(strs); //排序的话代码上比较简洁
        String min = strs[0]; //字典序最小
        String max = strs[strs.length - 1];//字典序最大

        String max = strs[0]; //不排序的话，可以单个比较，利用字符串的compareTo函数
        String min = strs[0];
        for(int i = 1;i<strs.length;i++){
            if(strs[i].compareTo(max) > 0){
                max = strs[i];
          }
            if(strs[i].compareTo(min) < 0){
                min = strs[i];
          }
        }
        //----------------------以下过程都一样-------------------------//
        int index = -1;
        for(int i = 0;i<min.length();i++){ //两者的最大公共前缀!
            if(min.charAt(i) != max.charAt(i)){
                break;
            }
            index = i;
        }
        if(index == -1){
            return "";
        }else{
            return min.substring(0,index + 1);
        }
    }

嗯。。。。。。。看到前缀这个字眼莫名的就能想到前缀树，给一个前缀树的实现代码

package ddx.september.day29;

import ddx.september.day28.Normal_31;

import java.util.Arrays;

public class Normal_14{
    public static void main(String[] args){
        Normal_14 demo = new Normal_14();
        String s = demo.longestCommonPrefix(new String[]{"fl","flower","flo"});
        System.out.println(s);
    }
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }
        String max_common = "";
        TrieNode cur = trie.root;
        while (cur.count == 1 && cur.end == 0){
            for (int i = 0; i < 26; i++) {
                if (cur.map[i] != null) {
                    max_common += (char) (i + 'a');
                    cur = cur.map[i];
                    break;
                }
            }
        }

        return max_common;
    }
}

class Trie {
    public TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }
//构造前缀树的插入方法
    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] arr = word.toCharArray();
        TrieNode node = root;
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i] - 'a';
            if (node.map[cur] == null) {
                node.map[cur] = new TrieNode();
                node.count++;
            }
            node = node.map[cur]; //结点已经创建，继续向下更新
            node.path++; //结点数加一
        }
        node.end++;
    }
}

//前缀树结点
class TrieNode {
    int path; //公用这个节点的单词数
    int end;  //以这个结点结束的单词数
    int count; //子结点的数量
    public TrieNode[] map;

    public TrieNode() {
        this.end = 0;
        this.path = 0;
        this.count = 0;
        this.map = new TrieNode[26];
    }

}

本作品采用《CC 协议》，转载必须注明作者和本文链接