What does Longest Common Prefix mean ?


  • 62
    V

    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?


  • 89
    V

    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.


  • 0
    W

    Please refer to my solution here

    http://whiteboardcoding.blogspot.com/2015/05/longest-common-prefix.html

    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


  • 13
    M

    They should put your example in the question


  • 1
    U

    I agree, it's confusing


Log in to reply
 

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