Longest Word in Dictionary through Deleting

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:

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

Analysis:

Two pointer 的变形题，一开始的想法是通过two pointer找到valid的result，然后store在list里，最后为了lexicographical sort，用key=lambda x：(-len(x),x)

improve:

可以先把d sort一遍，然后直接return第一个值

further improve：

用iter（）甚至更快

def findLongestWord(self, s, d):
 “””
 :type s: str
 :type d: List[str]
 :rtype: str
 “””
 result = []
 for each in sorted(d, key = lambda x: (-len(x), x)):
   i, j = 0, 0
 
   while j < len(each) and i < len(s):
     if s[i] == each[j]:
       j += 1
       i += 1
     else:
       i += 1
   if j == len(each):
     return each
 
 return “”
class Solution(object):
 def findLongestWord(self, s, d):
 “””
 :type s: str
 :type d: List[str]
 :rtype: str
 “””
 result = []
 for word in sorted(d, key = lambda x: (-len(x), x)):
   it = iter(s)
   if all(char in it for char in word):
   return word
 
 return “”

iter（）return一个iterator

它可以remember state，然后自动point到下一个，如果不在里面就直接走到end of iteration，这样char in it就return false

all（）会aggregate所有bool，只要有一个false就return false