-1

I'm a newbie in LeetCode and I'm working on the easy question: Longest Common Prefix. I couldn't pass one of the test cases: strs = ["flower","flower","flower","flower"]
I got an output=''

Here's the question: 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 "".

input:strs = ["flower","flower","flower","flower"] expected output: "flower"

While I checked my codes on both VSCode and Python Tutor code visualizer, I got the right output.

If someone can help me find out the bug I would be really grateful!

Appreciate it!

BTW the screenshot is my code (look ugly though :(

Feel free to give out some suggestions and solution. Thanks!

class Solution(object):
def longestCommonPrefix(self,strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    length = len(strs)
    dict = {}
    for i in strs:
        for j in list(i):
            if j not in dict:
                dict[j] = 1
            else:
                dict[j] += 1
    prefix = ""
    index = 0
    for k in dict:
        if dict[k] == length:
            for char in strs:
                if  k != char[index]:
                    return prefix
            index += 1
            prefix += k
    return prefix
archlotteatir
  • 3
  • 3
  • Welcome to Stack Overflow. Leetcode has its own forum/discussions section and this question would be better suited there. Also, it would be helpful to directly link to the problem in question so we can see the full requirements. – SimonUnderwood Apr 28 '23 at 14:07
  • Sure! Here's the link: https://leetcode.com/problems/longest-common-prefix/description/ – archlotteatir Apr 28 '23 at 14:08
  • Do you know what version of Python is used by Leetcode? Your code relies on `for k in dict` retrieving the keys in the order you added them. That will not necessarily work on Python 3.6 or below: https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6 – slothrop Apr 28 '23 at 14:52
  • 1
    (Also, best not to use `dict` as a variable name since it's a builtin class.) – slothrop Apr 28 '23 at 14:52

1 Answers1

0

There are issues with your algorithm. Counting the letters in a dictionary does not ensure that they are at the same positions consecutively (e.g. what if the same letter is present multiple times in a string, or in all strings).

A simple algorithm for this would be to go through each position starting with zero advancing up to the point where not all strings have the same letter at that position. This will give you the length of the common prefix. You can get the prefix itself from any of the string in the list (getting the first X letters)

The whole thing can fit in a single line, using the next function to advance through the positions and zip to get all letters grouped by "column"

strs[0][:next((i for i,s in enumerate(zip(*strs)) 
                 if len(set(s))>1),min(map(len,strs)))]
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • Thank you answering the question! The idea you provided is really powerful. However it still can't pass one of testcases: strs= ['ab','a'] I will take a look other solutions and keep on working on it! Thanks a lot! – archlotteatir Apr 29 '23 at 11:51
  • There as indeed a mistake in my solution, When the common prefix was a whole string and the first element was longer, it was taking the first complete first string instead of using the length of the smallest string. (which was the prefix in that case) – Alain T. Apr 29 '23 at 18:51
  • I tried again and it did pass! Thanks a lot for providing such powerful solution! (This solution is the shortest code I've ever seen in term of this problem! Appreciate it. – archlotteatir Apr 30 '23 at 14:09