• 39.8%

https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/?tab=Description

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.

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.

https://discuss.leetcode.com/topic/80799/short-java-solutions-sorting-dictionary-and-without-sorting

Short Java Solutions - Sorting Dictionary and Without Sorting

We sort the input dictionary by longest length and lexicography. Then, we iterate through the dictionary exactly once. In the process, the first dictionary word in the sorted dictionary which appears as a subsequence in the input string s must be the desired solution.

An alternate, more efficient solution which avoids sorting the dictionary:

Time Complexity: O(nk), where n is the length of string s and k is the number of words in the dictionary.

https://discuss.leetcode.com/topic/80887/short-python-solutions

Short Python solutions

More efficient version (no sorting):

Different style:

Optimized as suggested by @easton042, testing from longest to shortest and returning the first valid one without testing the rest:

Or:

And taking that even further by not sorting unnecessarily much:

https://discuss.leetcode.com/topic/80876/10-lines-solutions-for-c

10 lines solutions for c++

I think there is no need to sort the dic, just iterate the dic and test whether the word is satisfied and whether we need update our answer.

https://discuss.leetcode.com/topic/80816/python-simple-two-pointer

Python Simple (Two pointer)

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.

my code: