Python solution via sorting and hashset with explanation


  • 0
    Z

    First sort the list by length then alphabetically. Then, iterate through the sorted list. If the length of word is 1, just add to hashset. If length larger than one, we need to check whether its [:-1] part in set or not. So all the content in hashset are strings meet our requirements. In order to meet the output requirement, we first sort alphabetically then by length. Pick the one on the top.

    class Solution(object):
        def longestWord(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            if not words:
                return ""
            
            words.sort(lambda x, y: len(x) - len(y))
            words.sort()
            
            hashset = set()
            
            for i in range(0, len(words)):
                if len(words[i]) == 1:
                    hashset.add(words[i])
                elif words[i][:-1] in hashset:
                    hashset.add(words[i])
            
            if not hashset:
                return ""
    
            if len(hashset) == 1:
                return ""
           
            res = list(hashset)
        
            res.sort()
            res.sort(lambda x, y: len(y) - len(x))
            
            print res
            
            return res[0]
    

  • 1
    Z

    A cleaner version is written below. In addition, I believe there should add another test case ["a"] for example. It should be correct? In correct? I don't know, but both situation passed.

    class Solution(object):
        def longestWord(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            if not words:
                return ""
            
            words.sort(lambda x, y: len(x) - len(y))
            words.sort()
            
            hashset = set()
            
            for i in range(0, len(words)):
                if len(words[i]) == 1:
                    hashset.add(words[i])
                elif words[i][:-1] in hashset:
                    hashset.add(words[i])
            
            if not hashset:
                return ""
           
            res = list(hashset)
        
            res.sort()
            res.sort(lambda x, y: len(y) - len(x))
            
            return res[0]
    

  • 0
    C

    @zhtpandog Hi, I am new to Python. Can you explain how does
    """
    words.sort(lambda x, y: len(x) - len(y))
    """
    sort the listy by length?

    I tested it with words.sort(key=len) on a random list, and they give the same results. Cant figure out myself. Thanks!


  • 0
    Z

    @cantarrella yes, it is sorting by length. It is same as key = len.
    It is just another way to write it.
    In python, if you are designing a class by yourself and you want different instances of them can be compared, you need to write cmp or lt functions. A value <0 means smaller, =0 means equal, and >0 means larger.
    You can find more info if you search cmp or lt on Google.


  • 0
    C

    @zhtpandog I got it. Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.