@xiaofeihuang85 agree, but when submitted in c# it is marked as incorrect (see attached image)
Any ideas?
@xiaofeihuang85 agree, but when submitted in c# it is marked as incorrect (see attached image)
Any ideas?
@arnshea I got the same "Wrong Answer" as well. I suggest to ignore this problem and move on lol
I didn't see this approach in article:
My idea seems more simple: Find smallest string in array (one pass). We know the common prefix must be in this string, lets call it "minString". Begin with the whole minString, and compare to each other string in array, checking if it str.startsWith(minstring). If no, take minString = minString.subString(0, length-1), and continue this until each other string starts with minString, and return that as result.
Time complexity is O(N * S^2) where S is the length of the smallest string.
Space complexity is O(1) or I suppose you could describe it as O(S) if the smallest string is variable length
@arnshea In your example stated below, there is no common prefix that can be applied to ["a", "a", "b"] so the correct answer is "". It's not a majority rule. The longest prefix needs to exist in all strings in the array, and in the case above, there is no prefix that meets that condition (hence the "" expected result). So in the case of: ["friend", "flap", "fire"], the correct response would be: "f", and in the case of ["door", "dead", "bird"], the answer would also be: ""
@xiaofeihuang85 that's what I figured but I was assuming common meant "most" not "all". I've added a hint that makes "all" clear.
@causaelity good call, I've added a hint in case anyone else misinterprets it like I did.
@Darren_Zhang time complexity of Approach #1 is log(n**2) when they have the same str
@yanwen4 If all strings are equal, how can you get s2.indexOf(s1) != 0. The first time s2.indexOf(s1) is 0.
52 ms Python 3 brute-force solution:
class Solution:
def longestCommonPrefix(self, strs):
if not strs or strs[0] == '':
return ''
prefix = strs[0]
for i in range(1, len(strs)):
match = re.match(prefix, strs[i])
while not match:
prefix = prefix[:-1]
match = re.match(prefix, strs[i])
return prefix