Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objec­tive: Write an algo­rithm to find The Longest Sequence Of Pre­fix Shared By All The Words In A String. This inter­est­ing prob­lem was asked in the Google inter­view for soft­ware engi­neer. This prob­lem is bit tricky, it looks dif­fi­cult but actu­ally it is sim­ple problem.

Input: A String

Out­put: The longest sequence of pre­fix com­mon in all the words in a string

Exam­ple:

Bed­room Bed­Clock Bed­Table Bed­Wall” => “Bed”

Approach:

  • Split the input by blank space and store it in arrA[].
  • Cre­ate int resultLen and store the first index string length in it (int resultLen = arrA[0].length())
  • Cre­ate another interger vari­able, int curr
  • Now run a loop in rest of the array.
  • Check if curr < resultLen and curr<length of cur­rent string in a loop
  • If so check if char­ac­ter at curr posi­tion matched in first index string and with the cur­rent string a loop, if so, increase curr by 1
  • Change resultLen = curr
  • Return sub­string of resultLen length

Com­plete Code:

Output:
Original String : Sumit Summation Summit Sum
Common Prefix is : Sum

 

You may also like...

  • Muthu

    Good start.
    But i see some code not appro­pri­ate. I believe if the code is run on this
    Sumit Muthu Sum­ma­tion Sum­mit Sum, it will not give desired out­put. You need to tweak your while loop.
    while (curr < resultLen && curr < arrA[i].length()
    && arrA[0].charAt(curr) == arrA[1].charAt(curr))

    you have to keep track of prev and com­pare the curr with that, not just [0] and [1]

    • Sumit Jain

      Thanks Muthu for point­ing it out, i had put “1” instead of “i”. Cor­rected it

      Sumit

  • Sumeet Van­daku­dri

    Your code fails for {“a”, “a”, “b”} The out­put should be “” but your code give “a” as out­put !
    Cor­rect me if i am wrong!!