LeetCode刷题【14】最长公共前缀

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

字典树解法

思路

字符串搜索匹配中常用的方法之一字典树，用在这里还是很方便的

1. 遍历String[] strs构建字典树
2. 从字典树的根节点看是往下找只有一个子节点的情况，把这个自己点转化为char字符记下来
3. 不光是只有一个的子节点的情况。如果说遇到的节点是标记为了字符串结尾的话，也应当结束，因为记录下来的字符组成的字符串已经达到了某个字符串的长度了

一点思考

代码中的getSingleChild()方法是判断这个节点是否只有一个子节点的，用了个遍历26个字母的方法

如果只有一个子节点的话，会返回那个子节点对应的下标，从而可以重新转换为char字符。

不过可以再优化调整下，我们可以在Node节点中再增加一个字段标记当前节点下面有多少个不同的子节点，而需要操作就变为，当在Node的children上构建新子节点的时候，同时给这个统计字段+1，这样我们在后面遍历搜索的时候就可以直接判断了

代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Trie trie = new Trie();

        for (String str : strs) {
            trie.insert(str);
        }


        return trie.longestCommonPrefix();
    }



    class Trie{

        Node root = new Node();

        public void insert(String str){
            if (null == str){
                return;
            }
            int idx = -1;
            Node cur = root;
            while (++idx < str.length()){
                int i = str.charAt(idx) - 'a';
                if (cur.children[i] == null){
                    cur.children[i] = new Node();
                }
                cur = cur.children[i];
            }
            cur.flag = true;
        }


        public String longestCommonPrefix(){
            StringBuffer sb = new StringBuffer();
            Node cur = root;
            int idx = getSingleChild(cur);
            while (idx != -1){
                if (cur.flag){
                    break;
                }
                //记char
                sb.append((char)('a'+idx));
                //找下一个
                cur = cur.children[idx];
                idx = getSingleChild(cur);
            }
            return sb.toString();
        }

        private int getSingleChild(Node node){
            int singleChild = -1;
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i]!=null){
                    if (singleChild!=-1){
                        return -1;
                    }
                    singleChild = i;
                }
            }
            return singleChild;
        }

        class Node{
            boolean flag;
            Node[] children;
            public Node(){
                flag = false;
                children = new Node[26];
            }
        }
    }
}

改了一下，完全没提升

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }
        return trie.longestCommonPrefix();
    }


    class Trie {

        Node root = new Node();

        public void insert(String str) {
            if (null == str) {
                return;
            }
            int idx = -1;
            Node cur = root;
            while (++idx < str.length()) {
                int i = str.charAt(idx) - 'a';
                if (cur.children[i] == null) {
                    cur.children[i] = new Node();
                    cur.childrenCount++;
                }
                cur = cur.children[i];
            }
            cur.flag = true;
        }


        public String longestCommonPrefix() {
            StringBuffer sb = new StringBuffer();
            Node cur = root;
            int idx = cur.getSingleChild();
            while (idx != -1) {
                if (cur.flag) {
                    break;
                }
                //记char
                sb.append((char) ('a' + idx));
                //找下一个
                cur = cur.children[idx];
                idx = cur.getSingleChild();
            }
            return sb.toString();
        }

        class Node {

            boolean flag;
            Node[] children;
            int childrenCount;

            public Node() {
                childrenCount = 0;
                flag = false;
                children = new Node[26];
            }

            public boolean isSingleChild() {
                return childrenCount == 1;
            }

            public int getSingleChild() {
                if (isSingleChild()) {
                    for (int i = 0; i < children.length; i++) {
                        if (children[i] != null) {
                            return i;
                        }
                    }
                }
                return -1;
            }
        }
    }
}