Longest Common Prefix
You're given an array of strings strs. Return the longest string that every element of strs starts with. If the strings don't all share the same first character, or any of them is empty, return the empty string "". With a single string, the whole string is the answer.
Examples
strs = ["flower","flow","flight"] returns "fl"
All three start with "fl". At the third character, flower and flow have an o where flight has an i.
strs = ["dog","racecar","car"] returns ""
The first characters already differ, so the common prefix is empty.
strs = ["ab","a"] returns "a"
The prefix can be no longer than the shortest string, which is "a".
Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.
Hints
A common prefix grows one character at a time. What has to be true of every string for the prefix to grow by one more?
Scan by character position, checking the same index in every string before moving on.
For i over the first string's indices, if any other string has length <= i or a different character at i, return the first string's first i characters. After the loop, return the first string.
Drill This: Your Approach First
Approach
Compare the strings one column at a time. For each index i of the first string, check that every other string is long enough to have a character at i and that it matches. At the first string that runs out or differs, the prefix is the first string's first i characters. If every column matches, the whole first string is the prefix. Each character is read at most once, and the scan stops at the first mismatch.
Time
O(S)
Space
O(1)
Pitfall
Solutions
class Solution {
public String longestCommonPrefix(String[] strs) {
String first = strs[0];
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return first.substring(0, i);
}
}
}
return first;
}
}class Solution:
def longestCommonPrefix(self, strs) -> str:
first = strs[0]
for i, c in enumerate(first):
for s in strs[1:]:
if i >= len(s) or s[i] != c:
return first[:i]
return first