Longest Common Prefix - Leetcode 14 - Python

i did if the length of the set of the indexed letters is equal to 1, then append that to out and keep going until there are multiple letters in the set - this beat 80 or so percent

I came up with a solution, but with more optimization. Let me explain:
Time complexity O(2n)
Space Complexity O(1)

1. First, we find the shortest string in the array and store it in a variable called 'ans.' We then remove this shortest string from the array.
2. Next, we iterate through all the remaining strings one by one. For each string, we check if the last character of 'ans' matches the character at the same index in the current string.
3. If there is a match, we move on to the next iteration.
4. If there is no match, we remove the character from our 'ans' variable and enter a loop. In this loop, we continue checking the second-to-last character of 'ans' and so on, until 'ans' becomes empty."

Did it work? Yes. Did it make sense? No.

im not sure how you added I == Len(s) *what purpose it serves

could you reiterate concept of inbound and outbound?

Why don't use sorted like others:

class Solution:
def longestCommonPrefix(self, v: List[str]) -> str:
ans=""
v=sorted(v)
first=v[0]
last=v[-1]
for i in range(min(len(first),len(last))):
if(first[i]!=last[i]):
return ans
ans+=first[i]
return ans

Thanks for the video))

thanks for the code i was trying to do this but wasn't able to

we are using for loop inside another for loop. isnt the time complexity n2? Exponential

how can you say its O(n) when you have nested loops lol. Its O(n*m)

Why isn't the time complexity O(n^2)? There's a nested for loop

Thanks!

I don't understand how res+ = strs[0][i] would only contain what is common to all the strings. For example, when i = 2,
won't res = res+strs[0][2] which is "fl"+"o".
*consider the {"flower","flow","flight"} example.
Some help pls

Here are some optimization recommendations:
Adding to a string in Python, will always create a new string, which is not optimal.
We dont even have to store any information.
We can just return the slice up to index i (exclusive), as soon as any two characters are not equal or any index is out of bounds.

def longestCommonPrefix(self, strs: List[str]) -> str:
for i in range(len(strs[0])):
for j in range(1, len(strs)):
if i == len(strs[j]) or strs[0][i] != strs[j][i]:
return strs[j][:i]
return strs[0]

isn't it a O(n^2) solution?

This is an amazing solution - looping over the same character index of every string at once. Another solution I came up with that was intuitive to me:
1. Find the shortest string (since the prefix can't be longer than the shortest string) - O(n)
2. Set the prefix to this shortest string (in theory the entire shortest string can be the prefix)
3. compare shortest string with every other string character by character - O(n)
4. at the first character mismatch, if we haven't looped over the entire short string (prefix), update prefix to this shortened version

There are two passes, but the time complexity is still O(n)

# set prefix to first str by default
prefix = strs[0]
# prefix can't be longer than the shortest str, so we need to find it
for s in strs: # O(n)
prefix = prefix if len(prefix) < len(s) else s


for s in strs:
iP, iS = 0, 0 # index of prefix, index of current string
while iP < len(prefix) and iS < len(s): # make sure neither index is out of bounds
if prefix[iP] == s[iS]: # match? simply increment both indices
iP+=1
iS+=1
else: # first mismatch
if len(prefix[0:iP]) < len(prefix):
prefix = prefix[0:iP] # set prefix to the shorter of two
iP = len(prefix) # exit while loop

return prefix

Isn't adding string to already contructed string bad practice?
What if we keep letters in list/array , than we can join them together?
Instead of s = s + new_letter,
we could do [ ... ] .append(new_letter) and finally return "".join( [ ... ] )

would it be more efficient to sort the list and compare the first and the last element in the sorted list, instead of comparing every single element to the s[0]?
sorting would be O(n logn)
and comparing the first and the last element would be O(n), i believe. idk if I'm missing somethign.

class Solution(object):
def longestCommonPrefix(self, strs):
sorted_strs = sorted(strs)
res = ''
i = 0

f_str = sorted_strs[0]
l_str = sorted_strs[-1]

while i < len(f_str) and i < len(l_str):
if f_str[i] == l_str[i]:
res += f_str[i]
i+=1
else:
return res
return res

c++ version:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string rsl = "";
for (int i = 0; i < strs[0].size(); i++) {
for (auto& s : strs) {
if (i == s.size() || s[i] != strs[0][i]) {
return rsl;
}
}
rsl += strs[0][i];
}
return rsl;
}
};

now i understand my mistake.
i was comparing with the "i" in range, so 0,1,2,3 with the length, so len() which gives out 4. with the understanding they should be the same, forgot that len() gives the amount, not like an index..
damn im a noob