Longest Common Prefix


  • 0
    Y

    @elmirap Get it! Thanks a lot!


  • 0
    W

    In approach 4, why is that:The algorithm makes log(n) iterations.
    Iteration seems determined by the length of common prefix m.
    Maybe I misunderstand the meaning of n?


  • 0
    B

    For Approach 1), it cuts the tail character of prefix, how to guarantee it is correct, why it is not the head character?

    say 'ttde' and 'abcdes' where 'ttde' is the first string and is started as prefix - it will continuously cut 'ttde' till empty, instead of returning the LCP 'de'


  • 0

    The approach 1's complexity is not O(s)
    eg:
    string 0: aaaaabbbbb
    string 1: aaaaaaaabbbbbbbb
    string 2: a
    string 3: a
    .....

    No matter you use find() in cpp or indexOf(), this is the strstr() function actually and it is O(len0 + len1) when you it is implemented in KMP.
    But you need use at most len0 times, it is O(len0 * (len0 + len1)). When you use S to represent total characters in the strings, it should be len0 + len1 +...

    Obviously, O(len0 * (len0 + len1)) and O(S) is totally different even they have positive correlation, but it is not in linear positive correlation.


  • 0
    F

    An optimization to #1 that makes it as good as #2 is to first find the minimum length of all strings (minLen).
    Then when comparing prefixes, do not compare more than minLen characters.


  • 0
    V

    @biolearning prefix means 'at the beginning'. 'tt' is a prefix for ttde. 'de', 'td' are not prefixes.


  • 0
    Y

    The trie approach doesn't make sense for this LCP problem. You could just save the LCP(S) and compute LCP(LCP(S), q). The trie approach is good for shortest unique prefix of q (that is not a prefix of any string in S), because you need to look at every string in S to determine whether the prefix is unique or not.


  • 0
    J

    Though I solved thisquestion it made me crazy! In my opinion,the description is not clear,one string return itsels?How explain the meaning of common?


  • 0
    P

    The Trie solution is messed up.

    1. Where did String 'q' come from ? Is it just any random String from the array of Strings ?
    2. In the implementation of TrieNode, it was declared as an array and in the function, the HashMap functions are used from the Implementation of Trie Solution.

  • 0
    I

    when I submit my answer,the submission result board tells me that :
    Input: ["aca","cba"]
    Output: "a"
    Expected: ""
    Did I misunderstand the meaning of 'prefix' ?


  • 0
    A

    @iamyong the question is asking for prefixes that are common among every string in the array. "aca" and "cba" has no common prefix so its output is empty. If it was "aca" and "aba" it would output "a". :)


  • 0
    C

    Great solution!!!


  • 0
    G

    I like the divide and conquer one.


  • 0
    D

    Since "vertical scanning" is the fastest, the lowest memory consumption, simple enough and quite straight forward, why bother others?


  • 0
    J

    I would recommend making the problem description a bit more detailed. I understood that the longest common prefix would be the longest equal prefix of two strings in the array rather than of all strings. Maybe adding an example makes it more clear.


  • 0
    M
    This post is deleted!

  • 0
    F

    If you sort the array alphabetically, then you will only need to find the common prefix between strs[0] and strs[strs.length - 1].


  • 0
    A

    I think there is a problem with a test case. If I read it properly the input strings are "a", "a", "b" (not using test case/flat binary 2i-1 syntax because I don't understand it) but the test expects "" (the empty string) as the output?

    Isn't the longest common prefix of "a", "a", "b" equal to "a"??


  • 0
    A

    The solution is wrong.
    input strings: "a", "a", "b", "ba", "bb"
    human answer: b or a depending on unspecified assumption first or last one wins
    INCORRECT expected answer: "" ?????


  • 0
    X

    The longest common prefix of "a", "a", "b" is supposed to be "a"


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.