LeetCode - Longest Common Prefix
Problem description
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 “”.
Example 1:
1
2
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
Analysis
Brute force solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class LongestCommonPrefix {
public String longestCommonPrefix(String[] strs) {
// miss this but AC
if (strs == null){
return "";
}
StringBuilder sb = new StringBuilder();
int index = 0;
int len = Integer.MAX_VALUE;
for(String s: strs){
len = Math.min(len, s.length());
}
if (strs.length == 0){
return "";
}
while (index < len){
char common = strs[0].charAt(index);
boolean shouldAdd = true;
for (String s:strs){
if (s.charAt(index) != common){
shouldAdd = false;
break;
}
}
if (shouldAdd){
sb.append(common);
}
else {
break;
}
index++;
}
return sb.toString();
}
}
What to improve
- missed the input is null edge case.