分类:字符串-子序列
题目描述:
给你一个字符串 s 和一个字符串数组 dictionary 作为字典,找出并返回字典中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个,返回长度最长且字典序最小的字符串。如果答案不存在,则返回空字符串。
class Solution: def findLongestWord(self, s: str, dictionary: List[str]) -> str: dictionary.sort(key = lambda x:(-len(x),x)) #列表按照字符串由长到短排序,相同长度的字符串,按照字典升序排列,注意-len() index = 0 #从索引0开始 for word in dictionary: #遍历列表中的每一个字符串 for char in word: #遍历字符串中的每一个字母 #从索引Inde(为什么要从Index开始,因为现在的char要从Index开始后面的字母中找,因为word中char前的字符在Index之前找到了)开始是否有字母char,如果无则返回-1,如果有则返回字母char在s中的索引,并且加1,为下一次的索引开始位置 index = s.find(char,index) + 1 if index == 0: #因为当Index==0时,说明此char在s中找不到,即word不是s的子序列 break if index != 0:#因为后面的字符串肯定比当前的短或者字典顺序更大 return word return ''