動機

類似word break去硬幹

Problem

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

 

Example 1:

Input: words = [w,wo,wor,worl,world]Output: worldExplanation: The word world can be built one character at a time by w, wo, wor, and worl.

Example 2:

Input: words = [a,banana,app,appl,ap,apply,apple]Output: appleExplanation: Both apply and apple can be built from other words in the dictionary. However, apple is lexicographically smaller than apply.

 

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 30
  • words[i] consists of lowercase English letters.

Sol

不過如果要用bisect在string上就只能sort而已，不能調其他東西

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()
        
        ret = ""
        for s in reversed(words):
            
            good = True
            for j in range(len(s)-1):
                k = bisect_left(words,s[:j+1])
                if k >= len(words) or 0 > k or words[k] != s[:j+1]:
                    #print("fail for", words[k] if 0<= k < len(words) else None ,s[:j+1])
                    good = False
                    break

            ret = s if good and len(s) >= len(ret) else ret
        return ret