What does Longest Common Prefix mean ?

  • 71

    The problem statement is confusing and unclear. Can someone throw light on this ?

    Is it to find prefix between each pair of strings and return the one which is longest. Or
    all the strings has to have a common prefix?

  • 99

    It seems that it is not to check between pair of strings but on all the strings in the array.

    For example:

    1. {"a","a","b"} should give "" as there is nothing common in all the 3 strings.

    2. {"a", "a"} should give "a" as a is longest common prefix in all the strings.

    3. {"abca", "abc"} as abc

    4. {"ac", "ac", "a", "a"} as a.

    Logic goes something like this:

    1. Pick a character at i=0th location and compare it with the character at that location in every string.

    2. If anyone doesn't have that just return ""

    3. Else append that character in to the result.

    4. Increment i and do steps 1-3 till the length of that string.

    5. return result.

    Make sure proper checks are maintained to avoid index out of bounds error.

  • -1

    Please refer to my solution here


    Programming Language: C#
    Run Time Complexity: if n is the length of shortest string in array of strings and there are m strings in the array. Run time complexity would be O(m*n)

    Space Complexity: Constant space

  • 15

    They should put your example in the question

  • 3

    I agree, it's confusing

  • 0

    @Vgn thanks.

  • 1

    I still have doubts regarding the question:

    For the input ["aca","cba"]
    expected output is ""
    Shouldn't it be a rather than "" ?

  • 0

    @Vgn Agreed....I had to read this https://stackoverflow.com/questions/34937067/prefix-of-a-string to figure out what a prefix is. The question should explain a little bit.

  • 0

    @vlodha93 for example:string "aca",it's prefix is:"a","ac" string "cba",it's prefix is:"c","cb",so the longest prefix among the two string is "", because there is no same prefix

Log in to reply

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