算法之字符串——最长公共前缀

1. 最长公共前缀

难度 简单:smirk:

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

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

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

:person_frowning:一开始的思路很简单,就是单纯的遍历所有字符串,两两比较,不断更新最长公共前缀的下标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;
    }

数据结构与算法——字符串

:raising_hand:这推荐一个评论的思路

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

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

代码如下
:eyes: :eyes: :eyes:

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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!