14.最长公共前缀

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

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

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

题解：

/**
    字典树TrieTree
 */
class Solution {
    public String longestCommonPrefix(String[] strs) {
        TreeNode root = new TreeNode();
        for (String str : strs) {
            if (str.equals("")) {
                return "";
            }
            createTrieNode(root, str);
        }
        String res = "";
        while (true) {
            int count = 0;
            for (int i = 0; i < 26; i++) {
                if (root.childs[i] != null) {
                    count++;
                }
            }
            if (count != 1) {
                return res;
            }
            for (int i = 0;i < 26; i++) {
                if (root.childs[i] != null) {
                    res += root.childs[i].data;
                    root = root.childs[i];
                    break;
                }
            }
            if (root.isEnd) {
                break;
            }
        }

        return res;
    }

    private void createTrieNode(TreeNode node, String str) {
        char[] arr = str.toCharArray();
        for (int i = 0;i < arr.length; i++) {
            int loc = arr[i] - 'a';
            if (node.childs[loc] == null) {
                node.childs[loc] = new TreeNode();
                node.childs[loc].data = arr[i];
            }
            node = node.childs[loc];
        }
        node.isEnd = true;
    }
}
class TreeNode {
    final static int MAX_SIZE = 26;
    char data;
    // 表示是否字符串的结尾
    boolean isEnd = false;
    TreeNode[] childs;

    public TreeNode() {
        childs = new TreeNode[MAX_SIZE];
        isEnd = false;
    }
}