LeetCode Solutions
524. Longest Word in Dictionary through Deleting
Time: $O(|\texttt{d}||\texttt{s}|)$ Space: $O(|\texttt{s}|)$
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
string ans;
for (const string& word : d)
if (isSubsequence(word, s))
if (word.length() > ans.length() ||
word.length() == ans.length() && word.compare(ans) < 0)
ans = word;
return ans;
}
private:
// Returns true if a is a subsequence of b
bool isSubsequence(const string& a, const string& b) {
int i = 0;
for (const char c : b)
if (i < a.length() && c == a[i])
++i;
return i == a.length();
};
};
class Solution {
public String findLongestWord(String s, List<String> d) {
String ans = "";
for (final String word : d)
if (isSubsequence(word, s))
if (word.length() > ans.length() ||
word.length() == ans.length() && word.compareTo(ans) < 0)
ans = word;
return ans;
}
// Returns true if a is a subsequence of b
private boolean isSubsequence(final String a, final String b) {
int i = 0;
for (final char c : b.toCharArray())
if (i < a.length() && c == a.charAt(i))
++i;
return i == a.length();
}
}
class Solution:
def findLongestWord(self, s: str, d: List[str]) -> str:
ans = ''
for word in d:
i = 0
for c in s:
if i < len(word) and c == word[i]:
i += 1
if i == len(word):
if len(word) > len(ans) or len(word) == len(ans) and word < ans:
ans = word
return ans