LeetCode 14 | Longest Common Prefix (Easy)
In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem Problem 1429. First Unique Number.
A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string.
Input: strs = ["flower","flow","flight"]
Input: strs = ["dog","racecar","car"]
Explanation: There is no common prefix among the input strings.
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]consists of only lower-case English letters.
You can find the problem here.
A prefix of a string is any substring that starts from the first character. The number of different prefixes of a string is equal to its length. For example, the string “flower” will have 6 different prefixes:
In the problem statement, we are given an array of strings. We have to return the longest string which occurs as a prefix in all our strings.
Is there any upper limit on the length of our answer string?
Yes. As said earlier, the number of different prefixes of a string is equal to its length. So the maximum possible length of the common prefix for a group of strings is equal to the length of the smallest string.
flowchartIn this the upper limit on LCP length is 4, and the length of answer is also 4
Answer = flow
Remember, the upper limit does not mean the length of our answer always!
flagIn this the upper limit on LCP length is 4, but the length of answer is 2
Answer = fl
minLen be the length of the smallest string. So from our observation, we can conclude that while finding the LCP we have to only consider the first
minLen characters of every string.
In the beginning, we may assume that all the strings do not share any common prefix. So our
ans variable will store an empty string. Then we will gradually expand our answer character by character. We will loop from the index
minLen-1. If all the strings have the same character at a given index, this means this character is a part of our LCP. We will append this character to our answer. But if we find an index
i at which all the strings do not share a common character, we will stop the process. After this, our answer string will not expand any further.
In the above example, our
minLen is 4. The character at the first two indexes are the same across all the strings, so they are part of our answer. The third character is not the same across all the strings, hence we stop our process and return the answer.
The time complexity of our solution is O(n*m), where n is the size of
strs array and
m is the length of the longest string in our array. In the worst case, we may have to check every character of all the strings. For example, we may have an array in which all the strings are equal.
The space complexity of our solution is O(1). Apart from the function argument(input) and our answer variable, we are only using some constant space that is independent of our input size.
Practice Makes Perfect
Can this problem be solved using a Trie data structure? Think about it.