最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

两种解法，

• 逐个字符对比，直接判断每个字符串的前缀，代码如下：

 public String longestCommonPrefix(String[] strs) {
        int minLength = Integer.MAX_VALUE;
        String minStr = "";
        for (String str : strs) {
            if (str.length() < minLength) {
                minStr = str;
                  minLength=str.length();
            }
        }
        if (minLength == 0 || strs.length==0) {
            return "";
        }
        for (int i = 0; i < minLength; i++) {
            char c = minStr.charAt(i);
            for (String str : strs) {
                if (str.charAt(i) != c) {
                    return minStr.substring(0, i);
                }
            }
        }
        return minStr;
    }

• 构造一个字典树（Trie），把所有的字符串都放到字典树里，然后求得最长公共前缀，代码如下：

class Solution {
   public String longestCommonPrefix(String[] strs) {
        Trie trie = new Trie();
        for (String s : strs) {
            trie.addWord(s);
        }
        return trie.getMaxPrefix();
    }
    static class Trie {
        private TrieNode root = new TrieNode(' ');
        public void addWord(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.childrens[c - 'a'] == null) {
                    node.childrens[c - 'a'] = new TrieNode(c);
                    node.increaseChildrenCount();
                }
                node = node.childrens[c - 'a'];
            }
            node.word = true;
        }
        private String getMaxPrefix() {
            TrieNode node = root;
            String prefix = "";
            while (node != null) {
                if (node.childrenCount != 1 || node.word) {
                    return prefix;
                }
                for (int i = 0; i < node.childrens.length; i++) {
                    if (node.childrens[i] != null) {
                        node = node.childrens[i];
                        break;
                    }
                }
                prefix += node.value;
            }
            return prefix.trim();
        }
    }
/**树节点
*/
    static class TrieNode {
        private char value;
        private TrieNode[] childrens;
        private int childrenCount;
        private boolean word;
        public TrieNode(char value) {
            this.value = value;
            this.childrens = new TrieNode[26];
        }
        public int getChildrenCount() {
            return childrenCount;
        }
        public void increaseChildrenCount() {
            childrenCount++;
        }
    }
}