Longest Common Prefix


  • 0
    A

    @xiaofeihuang85 agree, but when submitted in c# it is marked as incorrect (see attached image)0_1511207286437_LongestCommonPrefixResult.png

    Any ideas?


  • 0
    X

    @arnshea I got the same "Wrong Answer" as well. I suggest to ignore this problem and move on lol


  • 0
    W

    I didn't see this approach in article:
    My idea seems more simple: Find smallest string in array (one pass). We know the common prefix must be in this string, lets call it "minString". Begin with the whole minString, and compare to each other string in array, checking if it str.startsWith(minstring). If no, take minString = minString.subString(0, length-1), and continue this until each other string starts with minString, and return that as result.

    Time complexity is O(N * S^2) where S is the length of the smallest string.
    Space complexity is O(1) or I suppose you could describe it as O(S) if the smallest string is variable length


  • 0
    C

    @arnshea In your example stated below, there is no common prefix that can be applied to ["a", "a", "b"] so the correct answer is "". It's not a majority rule. The longest prefix needs to exist in all strings in the array, and in the case above, there is no prefix that meets that condition (hence the "" expected result). So in the case of: ["friend", "flap", "fire"], the correct response would be: "f", and in the case of ["door", "dead", "bird"], the answer would also be: ""


  • 0
    A

    @xiaofeihuang85 LOL, yep. Balanced parenthesis seems to work.


  • 0
    A

    @causaelity good call, that did it


  • 0
    B

    For the solution #4, the graph says 0 ... mid ... min, but the code has low = 1 which should be low = 0 to match the graph. Or the graph should be 1 ... mid .. min to match the code.


  • 0
    A

    @xiaofeihuang85 that's what I figured but I was assuming common meant "most" not "all". I've added a hint that makes "all" clear.


  • 0
    A

    @causaelity good call, I've added a hint in case anyone else misinterprets it like I did.


  • 0
    D

    I can't understand the Time complexity of Approach #1, Anyone can help me?


  • 0
    7

    @Darren_Zhang time complexity of Approach #1 is log(n**2) when they have the same str


  • 0
    A

    Analysis of Approach #4 says that algorithm makes log(n) iterations where n is the number of strings. But the binary search is applied on length and max value of that length can be m. So it seems to me that time complexity should be O(S∗log(m)) rather than O(S∗log(n))


  • 0

    Using trie to solve frequently querying is a great idea.


  • 0
    V

    time complexity of Approach 3 is wrong, as m is independent of n. Time complexity shoule be the number of leaves times O(m) instead of the height of tree times O(m). It should be O(m*n).


  • 0
    L

    @yanwen4 If all strings are equal, how can you get s2.indexOf(s1) != 0. The first time s2.indexOf(s1) is 0.


  • 0
    G

    Approach #1 should add one line :
    if (strs.length == 1) return strs[0];
    otherwise may occured ArrayIndexOutOfBoundsException.


  • 0
    P

    I don't get why we need a Trie for common querying. LCP(S) would always be a certain value, let's say x, therefore LCP(S + {q}) will be the same as LCP({x, q}) and so we need just to store x instead of the whole S.
    What I'm missing here? 🤔


  • 0
    N

    agree with pelligra, don't think we need a Trie here


  • 0
    H

    @gouhaonan, agree with you


  • 0
    M

    52 ms Python 3 brute-force solution:

    class Solution:
    def longestCommonPrefix(self, strs):
    if not strs or strs[0] == '':
    return ''
    prefix = strs[0]
    for i in range(1, len(strs)):
    match = re.match(prefix, strs[i])
    while not match:
    prefix = prefix[:-1]
    match = re.match(prefix, strs[i])
    return prefix


Log in to reply
 

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