美文网首页
最长公共前缀

最长公共前缀

作者: Jimhou | 来源:发表于2019-04-18 22:18 被阅读0次

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 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++;
        }
    }
}

相关文章

  • LeetCode 每日一题 [19] 最长公共前缀

    LeetCode 最长公共前缀 [简单] 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回...

  • 14. 最长公共前缀

    20180923-摘抄自14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,...

  • 5,最长公共前缀/数组与字符串

    最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例 1:...

  • Swift 最长公共前缀 - LeetCode

    题目: 最长公共前缀 描述: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""...

  • leetcode探索之旅(14)

    最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。 示例 1: ...

  • Leetcode 14 最长公共前缀

    最长公共前缀 题目 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例...

  • LeetCodeSwift 14.Longest Common

    题目 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例...

  • [day4] [LeetCode] [title14,122]

    14.最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串""。 示例 ...

  • 14. 最长公共前缀

    14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。 说明...

  • leetcode算法-最长公共前缀

    最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。 说明:所有输...

网友评论

      本文标题:最长公共前缀

      本文链接:https://www.haomeiwen.com/subject/qgvxgqtx.html