-
Notifications
You must be signed in to change notification settings - Fork 118
/
524. Longest Word in Dictionary through Deleting.cpp
71 lines (65 loc) · 2.22 KB
/
524. Longest Word in Dictionary through Deleting.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//Approach 1: Recursive Brute Force
//time: O(2^n), space: O(2^n)
//Approach 2: Iterative Brute Force
//time: O(2^n), space: O(2^n)
//Approach 3: Sorting and Checking Subsequence
//Runtime: 88 ms, faster than 64.35% of C++ online submissions for Longest Word in Dictionary through Deleting.
//Memory Usage: 15.5 MB, less than 100.00% of C++ online submissions for Longest Word in Dictionary through Deleting.
//time: O((nlogn + n)*x), x refers to average string length
//space: O(logn)
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
sort(d.begin(), d.end(), [](const string& a, const string& b){
return (a.size() == b.size()) ? a < b : a.size() > b.size();
});
for(string& word : d){
int wi = 0, si = 0;
while(wi < word.size() && si < s.size()){
if(word[wi] == s[si]){
wi++;
si++;
}else{
si++;
}
}
// cout << wi << "/" << word.size() << " " << si << "/" << s.size() << endl;
if(wi == word.size()){
return word;
}
}
return "";
}
};
//Approach 4: Without Sorting
//Runtime: 92 ms, faster than 44.98% of C++ online submissions for Longest Word in Dictionary through Deleting.
//Memory Usage: 23 MB, less than 7.69% of C++ online submissions for Longest Word in Dictionary through Deleting.
//time: O(nx), space: O(x)
class Solution {
public:
bool isSubsequence(string sub, string super){
//check whether sub is a substring of super
int i = 0, j = 0;
while(i < sub.size() && j < super.size()){
if(sub[i] == super[j]){
i++;
j++;
}else{
j++;
}
}
return i == sub.size();
};
string findLongestWord(string s, vector<string>& d) {
string ans = "";
for(string& word : d){
if(word.size() > ans.size() ||
(word.size() == ans.size() && word < ans)){
if(isSubsequence(word, s)){
ans = word;
}
}
}
return ans;
}
};