Longest Word in Dictionary through Deleting

• Time:O(|\texttt{d}||\texttt{s}|)
• Space:O(|\texttt{s}|)

C++

``````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:
// return 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();
};
};
``````

JAVA

``````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;
}

// return 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();
}
}
``````

Python

``````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
``````