Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"




Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"



Note:

All the strings in the input will only contain lower-case letters.
The size of the dictionary won't exceed 1,000.
The length of all the strings in the input won't exceed 1,000.

Difficulty: interview

Starter code:

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        

Solutions:
class Solution:
     def findLongestWord(self, s, d):
         """
         :type s: str
         :type d: List[str]
         :rtype: str
         """
         result = ''
         for word in d:
             lo = 0
             for l in word:
                 lo = s.find(l, lo)+1
                 if lo == 0:
                     break
             if lo > 0 and len(word) >= len(result):
                 if len(word) == len(result):
                     result = word if word < result else result
                 else:
                     result = word
         return result

class Solution:
     def findLongestWord(self, s, d):
         """
         :type s: str
         :type d: List[str]
         :rtype: str
         """
         def find(a,b):
             p = 0
             for c in b:
                 p = a.find(c,p) + 1
                 if p == 0:
                     return False
             return True
         
         ans = ''
         for word in d:
             if find(s,word):
                 if len(word) > len(ans):
                     ans = word
                 elif len(word) == len(ans) and word < ans:
                     ans = word
         return ans


class Solution:
     def findLongestWord(self, s, d):
         """
         :type s: str
         :type d: List[str]
         :rtype: str
         """
         
         def isMatch(s, w):
           index = 0
           
           for c in w:
             if c in s:
               index = s.find(c, index) + 1
               if index == 0:
                 return False
             else:
               return False
           return True
         
         candidates = []
         
         for word in d:
           if isMatch(s, word):
             candidates.append(word)
             
         candidates = sorted(candidates, key=lambda w:(len(w), w))
         if not candidates:
           return ""
         else:
           maxLen = len(candidates[-1])
           for c in candidates:
             if len(c) == maxLen:
               return c

class Solution:
     def findLongestWord(self, s, d):
         """
         :type s: str
         :type d: List[str]
         :rtype: str
         """
         word_dict = collections.defaultdict(list)
         for i, word in enumerate(d):
             word_dict[word[0]].append((i, word))
         
         res = ""
         for c in s:
             words_startswithc = word_dict[c]
             word_dict[c] = []
             for i, word in words_startswithc:
                 if len(word)==1: 
                     if len(d[i])==len(res):
                         res = min(res, d[i])
                     else: res = d[i] if len(d[i])>len(res) else res
                 else:
                     word_dict[word[1]].append((i, word[1:]))
         return res