算法-Trie树/- 最长公共前缀

深藏阁楼爱情的钟 2023-02-18 01:46 1阅读 0赞

# 算法-Trie树/- 最长公共前缀 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/longest-common-prefix/

## 1.2 题目描述 ##

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

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

示例 1:

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

输入: \[“dog”,“racecar”,“car”\]  
输出: “”  
解释: 输入不存在公共前缀。  
说明:

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

# 2 Trie树-递归版 #

## 2.1 思路 ##

构建Trie树，第一个单词先正常插入。

依次遍历后续单词，insert的时候如果发现一个字符在当前Trie树中不存在，说明只能由之前的所有字符构成公共前缀，直接返回即可。

如果存在，还需要判断当前查找长度是否大于之前最短前缀长度，大于就直接退出不再查找了。

## 2.2 代码 ##

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            String result = "";
            if(strs == null || strs.length == 0){ 
                return result;
            }
            Trie t = new Trie();
            String str = strs[0];
            String prefix = str;
            t.insert(str);
    
            for(int i = 1; i < strs.length; i++){ 
                String tmpPrefix = t.insertAndFindPrefix(strs[i], "");
                if(tmpPrefix.length() < prefix.length()){ 
                    prefix = tmpPrefix;
                    if(prefix.length() == 0){ 
                        // 如果发现已经没有公共前缀，直接退出查找
                        break;
                    }
                }
            }
            return prefix;
        }
    
        class Trie { 
            private Trie[] children;
            private boolean is_end;
            /** Initialize your data structure here. */
            public Trie() { 
                children = new Trie[26];
            }
            
            /** Inserts a word into the trie. */
            public void insert(String word) { 
                if(word == null || word.trim().length() == 0){ 
                    return;
                }
                char first = word.charAt(0);
                int index = first - 'a';
                Trie child = children[index];
                if(child == null){ 
                    child = new Trie();
                    children[index] = child;
                }
    
                word = word.substring(1);
                if(word.length() > 0){ 
                    child.insert(word);
                }else{ 
                    child.is_end = true;
                }
            }
    
            public String insertAndFindPrefix(String word, String prefix, int prefixLength) { 
                if(word == null || word.trim().length() == 0){ 
                    return prefix;
                }
                char first = word.charAt(0);
                int index = first - 'a';
                Trie child = children[index];
                if(child == null){ 
                    return prefix;
                }
                prefix = prefix + first;
                word = word.substring(1);
                if(word.length() > 0){ 
                    if(--prefixLength > 0){ 
                        prefix = child.insertAndFindPrefix(word, prefix, prefixLength);
                    }else{ 
                        return prefix;
                    }
                }else{ 
                    child.is_end = true;
                }
                return prefix;
            }
        }
    }

## 2.3 时间复杂度 ##

O(N\*L)

## 2.4 空间复杂度 ##

O(L)

# 3 Trie树-循环版 #

## 3.1 思路 ##

思路和前面差不多，不过这里优化先将最短字符插入，以便其他字符串插入查找时可以快速结束。

还有一个优化点是使用StringBuilder记录prefix，不然会创建大量String对象。

## 3.2 代码 ##

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            String result = "";
            if(strs == null || strs.length == 0){ 
                return result;
            }
            if(strs.length == 1){ 
                return strs[0];
            }
            Trie t = new Trie();
            int shortestIndex = -1;
            int shortestLength = Integer.MAX_VALUE;
            for(int i = 0; i < strs.length; i++){ 
                if(strs[i].length() == 0){ 
                    return result;
                } else if(strs[i].length() < shortestLength){ 
                    shortestLength = strs[i].length();
                    shortestIndex = i;
                }
            }
            String str = strs[shortestIndex];
            String prefix = str;
            t.insert(str);
    
            for(int i = 0; i < strs.length; i++){ 
                if(i == shortestIndex){ 
                    continue;
                }
                String tmpPrefix = t.insertAndFindPrefix(strs[i], new StringBuilder(), prefix.length());
                if(tmpPrefix.length() < prefix.length()){ 
                    prefix = tmpPrefix;
                    if(prefix.length() == 0){ 
                        // 如果发现已经没有公共前缀，直接退出查找
                        break;
                    }
                }
            }
            return prefix;
        }
    
        class Trie { 
            private Trie[] children;
            private boolean isEnd;
            /** Initialize your data structure here. */
            public Trie() { 
                children = new Trie[26];
            }
            
            /** Inserts a word into the trie. */
            public void insert(String word) { 
                Trie current = this;
                for(char c : word.toCharArray()){ 
                    int index = c - 'a';
                    Trie child = current.children[index];
                    if(child == null){ 
                        child = new Trie();
                        current.children[index] = child;
                    }
                    current = child;
                }
                current.isEnd = true;
            }
            
             /** Inserts a word into the trie. */
            public String insertAndFindPrefix(String word, StringBuilder prefix, int prefixLength) { 
                Trie current = this;
                for(char c : word.toCharArray()){ 
                    int index = c - 'a';
                    Trie child = current.children[index];
                    if(child == null){ 
                        return prefix.toString();
                    }
                    prefix.append(c);
                    if(--prefixLength == 0){ 
                        return prefix.toString();
                    }
                    current = child;
                }
                return prefix.toString();
            }
           
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200615104338671.png]  
O(N\*L)

## 3.4 空间复杂度 ##

O(L)

[20200615104338671.png]: https://img-blog.csdnimg.cn/20200615104338671.png