Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Leetcode problem 14. Longest Common Prefix (Python)

I tried to solve the problem (you can read description here: https://leetcode.com/problems/longest-common-prefix/) And the following is code I came up with.
It gives prefix value of the first string in strs list and compares prefix with every string from the list, popping all characters that are not equal.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = strs[0][0]
        for i in range(len(strs)):
            for j in range(len(prefix)):
                if strs[i][j] != prefix[j]:
                    prefix.pop(prefix[j])
        return prefix

But this code fails in the very first testcase where strs = ["flower","flow","flight"]
Expected output is "fl", while my code returns just "f"
I am struggling to find what is going wrong in my solution. Maybe you can help?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

Iterate over the characters in parallel with zip:

strs = ["flower", "flow", "flight"]

n = 0
for chars in zip(*strs):
    if len(set(chars)) > 1:
        break
    n += 1

# length
print(n) # 2

# prefix
print(strs[0][:n]) # fl

Similar approach as a one-liner using itertools.takewhile:

from itertools import takewhile

prefix = ''.join([x[0] for x in takewhile(lambda x: len(set(x)) == 1, zip(*strs))])
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading