524. Longest Word in Dictionary through Deleting

  • 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.

1
2
3
4
5
6
Example 1:
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"
1
2
3
4
5
6
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.

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.

1
2
3
4
5
6
7
8
9
10
public String findLongestWord(String s, List<String> d) {
Collections.sort(d, (a,b) -> a.length() != b.length() ? -Integer.compare(a.length(), b.length()) : a.compareTo(b));
for (String dictWord : d) {
int i = 0;
for (char c : s.toCharArray())
if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
if (i == dictWord.length()) return dictWord;
}
return "";
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
public String findLongestWord(String s, List<String> d) {
String longest = "";
for (String dictWord : d) {
int i = 0;
for (char c : s.toCharArray())
if (i < dictWord.length() && c == dictWord.charAt(i)) i++;

if (i == dictWord.length() && dictWord.length() >= longest.length())
if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
longest = dictWord;
}
return longest;
}

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

1
2
3
4
5
def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
return max(sorted(filter(isSubsequence, d)) + [''], key=len)

More efficient version (no sorting):

1
2
3
4
5
def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
return min(filter(isSubsequence, d) + [''], key=lambda x: (-len(x), x))

Different style:

1
2
3
4
5
6
7
8
def findLongestWord(self, s, d):
best = ''
for x in d:
if (-len(x), x) < (-len(best), best):
it = iter(s)
if all(c in it for c in x):
best = x
return best

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

1
2
3
4
5
6
def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
d.sort(key=lambda x: (-len(x), x))
return next(itertools.ifilter(isSubsequence, d), '')

Or:

1
2
3
4
5
6
def findLongestWord(self, s, d):
for x in sorted(d, key=lambda x: (-len(x), x)):
it = iter(s)
if all(c in it for c in x):
return x
return ''

And taking that even further by not sorting unnecessarily much:

1
2
3
4
5
6
7
8
9
def findLongestWord(self, s, d):
heap = [(-len(word), word) for word in d]
heapq.heapify(heap)
while heap:
word = heapq.heappop(heap)[1]
it = iter(s)
if all(c in it for c in word):
return word
return ''

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.

1
2
3
4
5
6
7
8
9
10
11
12
string findLongestWord(string s, vector<string>& d) {
string ans;
for (int i = 0; i < d.size(); i++) {
int pi = 0, pj = 0;
for (; pi < s.size() && pj < d[i].size(); pi++) {
pj += s[pi] == d[i][pj];
}
if (pj == d[i].size() && (ans.size() < d[i].size() || (ans.size() == d[i].size() && ans > d[i])))
ans = d[i];
}
return ans;
}

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.

1
2
3
4
5
6
7
8
9
10
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 ""

my code:

关键点,两个string的对齐 同时要读清题意,两个字符串长度相等,按照字典顺序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
string longest="";
for(int i=0; i<d.size(); i++){
int j=0;
if(d[i].size()<longest.size())
continue;
for(auto c:s){
if(c==d[i][j])
j++;
}
if(j==d[i].size() && d[i].size()>longest.size())
longest = d[i];
else if(j==d[i].size() && d[i].size()==longest.size() && d[i] < longest)
longest = d[i];
}
return longest;
}
};
谢谢你,可爱的朋友。