Leetcode 14. Longest Common Prefix
Problem Explanation
Given an array of strings, the task is to find the longest common prefix (LCP) that all the strings have. The prefix is the initial segment of a word. In this case, we need to find the longest initial segment that is common among all strings. If there's no common prefix, the function should return an empty string.
For example, in the array ["flower","flow","flight"]
, the LCP is fl
. For the array ["dog","racecar","car"]
, there is no LCP, hence the function should return "".
Solution Approach
We start from the first character of the first string and compare the corresponding characters with each string in the array. If the character is the same, we continue to the next character, otherwise, we return the substring from the first character to the character before the one causing the mismatch.
Using the example ["flower","flow","flight"]
, these are the steps:
- Start with the first string, 'flower'.
- Compare the first character 'f' of 'flower' with the first characters of other strings. They all have 'f', so we move to the next character.
- Next, compare the second character 'l' of 'flower' with the second characters of other strings. They all have 'l', so we move to the next character.
- Next, compare the third character 'o' of 'flower' with the third characters of other strings. 'flight' has 'i' instead of 'o', so we return the characters before this one, which is 'fl'.
Let's implement this approach in Python, Java, JavaScript, C++, C#.
Python Solution
1 2python 3class Solution: 4 def longestCommonPrefix(self, strs): 5 if not strs: 6 return "" 7 for i in range(len(strs[0])): 8 for str in strs: 9 if i == len(str) or strs[0][i] != str[i]: 10 return strs[0][:i] 11 return strs[0]
Here, strs[0]
is the first string in the array. We iterate through each character in this string, and then compare it with the corresponding character in all the other strings.
Java Solution
1
2java
3class Solution {
4 public String longestCommonPrefix(String[] strs) {
5 if (strs.length == 0)
6 return "";
7 for (int i = 0; i < strs[0].length(); i++) {
8 for (String str : strs)
9 if (i == str.length() || strs[0].charAt(i) != str.charAt(i))
10 return strs[0].substring(0, i);
11 }
12 return strs[0];
13 }
14}
This code works the same way as the Python code.
JavaScript Solution
1
2javascript
3var longestCommonPrefix = function(strs) {
4 if (!strs.length) return "";
5 for (let i = 0; i < strs[0].length; i++) {
6 for (let str of strs) {
7 if (i === str.length || strs[0][i] !== str[i]) {
8 return strs[0].substring(0, i);
9 }
10 }
11 }
12 return strs[0];
13};
Similar to the Python and Java solutions, we iterate over each character of the first string in the input array.
C++ Solution
1
2cpp
3class Solution {
4public:
5 string longestCommonPrefix(vector<string>& strs) {
6 if (strs.empty()) return "";
7 for (int i = 0; i < strs[0].length(); ++i)
8 for (int j = 1; j < strs.size(); ++j)
9 if (i == strs[j].length() || strs[j][i] != strs[0][i])
10 return strs[0].substr(0, i);
11 return strs[0];
12 }
13};
The C++ solution checks each character in the first string against the corresponding character in other strings.
C# Solution
1 2csharp 3public class Solution { 4 public string LongestCommonPrefix(string[] strs) { 5 if (strs.Length == 0) return ""; 6 for (int i = 0; i < strs[0].Length; i++) 7 for (int j = 1; j < strs.Length; j++) 8 if (i == strs[j].Length || strs[j][i] != strs[0][i]) 9 return strs[0].Substring(0, i); 10 return strs[0]; 11 } 12}
Similar to the previous languages, the C# solution iterates over the characters in the first string and compares them with the corresponding characters in other strings.Both the C# and C++ solution work similar to the solutions in Python, Java and JavaScript.
To conclude, this problem called longest common prefix can be solved by traversing from the first character of the first string and comparing the corresponding characters with each string in the array. The trick involves moving the index only when the characters of all strings match. If the character doesn't match, or you reach the end of any string, you return the common prefix found so far.
The solutions provided for Python, Java, JavaScript, C++, and C# all essentially use the same idea where they take the first string as base and compare each character in it with the corresponding characters in other strings. This approach is very efficient and straightforward, resulting in clean and easy-to-understand code. It's a good demonstration of how different languages can handle the same problem in a uniform way, making this a good problem for studying different programming languages.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.