Let's check whether each word is a subsequence of S individually by "best" order (largest size, then lexicographically smallest.) Then if we find a match, we know the word being considered must be the best possible answer, since better answers were already considered beforehand.
Let's figure out how to check if a needle (word) is a subsequence of a haystack (S). This is a classic problem with the following solution: walk through S, keeping track of the position (i) of the needle that indicates that word[i:] still remains to be matched to S at this point in time. Whenever word[i] matches the current character in S, we only have to match word[i+1:], so we increment i. At the end of this process, i == len(word) if and only if we've matched every character in word to some character in S in order of our walk.
def findLongestWord(self, S, D): D.sort(key = lambda x: (-len(x), x)) for word in D: i = 0 for c in S: if i < len(word) and word[i] == c: i += 1 if i == len(word): return word return ""
The same idea using python build-in function:
def findLongestWord(self, s, d): for word in sorted(d, key = lambda w: (-len(w), w)): it = iter(s) if all(c in it for c in word): return word return ''
Thanks for a simple and easy-to-understand explanation! Sometimes other people are so good and post answers that are super short/hard-to-understand. Thanks for keeping it real.
Here is my naive implementation
class Solution(object): def findLongestWord(self, s, d): """ :type s: str :type d: List[str] :rtype: str """ def is_subsequence(s,t): # check if t is subsequence of s i = 0 j = 0 m = len(s) n = len(t) if n > m: return False while i < m and j < n: if s[i] == t[j]: i += 1 j += 1 else: i += 1 return j == n subsequence_length = 0 subsequence = '' for string in d: if is_subsequence(s,string): if subsequence_length < len(string): subsequence = string subsequence_length = len(string) elif subsequence_length == len(string): subsequence = min(subsequence,string) return subsequence
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.