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))


Log in to reply
 

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