|
Be the first user to complete this post
|
Add to List |
14. Longest Shared Prefix Sequence in a String
Input: A String Output: The longest sequence of prefix common in all the words in a string
Example:
bedroom bedroot bedrod bedclock Output: Bed
Approach:
- Idea is to start with the first word in the input string and take the entire word length as N
- Now take then second word and update the N = length of shared prefix ( N characters of first word, second word).
- Now take then third word and update the N = length of shared prefix ( N characters of first word, third word).
- Repeat the above step until process all the words
- Now return N characters of first word as final result. shared prefix among all the words.
Walk through
Input = bedroom bedroot bedrod bedclock first word = bedroom N (prefix length) = 7 second word = bedroot 1st N(=7) characters of first word = bedroom shared prefix = bedroo N (shared prefix length) = 6 third word = bedrod 1st N(=6) characters of first word = bedroo shared prefix = bedro N (shared prefix length) = 5 fourth word = bedclock 1st N(=5) characters of first word = bedro shared prefix = bed N (shared prefix length) = 3 Result = 1st N(=3) characters of the first word = bed
Output:
Original String : bedroom bedroot bedrod bedclock Common Prefix is : bed