今天lintCode上面做了一道面试题，这道题不难，但是就是有多种的解法，所以觉得有必要记录下来，主要是这道题有字典树的解法~~~字典树相对另一种解法，复杂度没有明显的改善，这里只是为了记录多种方法。

1.概览

(1).题意

给k个字符串，求出他们的最长公共前缀(LCP)

(2).样例

在 "ABCD" "ABEF" 和 "ACEF" 中,  LCP 为 "A"
在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"

2.代码

  由于这道题非常的简单，就不用解释解题思路，最简单的方法就是暴力。

(1).传统解法--暴力法

public String longestCommonPrefix(String[] strs) {
        int minLength = Integer.MAX_VALUE;
        String minLengthString = null;
        for (int i = 0; i < strs.length; i++) {
            if (minLength > strs[i].length()) {
                minLength = strs[i].length();
                minLengthString = strs[i];
            }
        }
        for (int i = minLength; i >= 0; i--) {
            String string = minLengthString.substring(0, i);
            int j = 0;
            for (j = 0; j < strs.length; j++) {
                if(!string.equals(strs[j].substring(0, i))) {
                    break;
                }
            }
            if(j == strs.length) {
                return string;
            }
        }
        return "";
    }

(2).字典树

public class Solution {
    /*
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    public String longestCommonPrefix(String[] strs) {
                for(int i = 0; i < strs.length; i++) {
            if(strs[i].equals("")) {
                return "";
            }
        }
        DictionaryTree dictionaryTree = new DictionaryTree();
        for(int i = 0; i < strs.length; i++) {
            dictionaryTree.addWord(strs[i]);
        }
        return dictionaryTree.longestCommonPrefix();
    }
}
class DictionaryTree {
    TreeNode root;
    public DictionaryTree() {
        root = new TreeNode(' ');
    }
    public void addWord(String word) {
        TreeNode node = root;
        for(int i = 0; i < word.length(); i++) {
            if(!node.map.containsKey(word.charAt(i))) {
                node.map.put(word.charAt(i), new TreeNode(word.charAt(i)));
                node.len++;
                node.c = word.charAt(i);
            }
            node = node.map.get(word.charAt(i));
        }
    }
    public String longestCommonPrefix() {
        StringBuilder stringBuilder = new StringBuilder("");
        TreeNode node = root;
        while(node.len == 1) {
            stringBuilder.append(node.c);
            node = node.map.get(node.c);
        }
        return stringBuilder.toString();
    }
    private class TreeNode{
        char value;
        Map<Character, TreeNode> map = null;
        int len = 0;
        char c = ' ';
        public TreeNode(char value) {
            this.value = value;
            map = new HashMap<>();
        }
    }
}