Longest Word in Dictionary through Deleting
Medium · Two Pointers · Explanation and code example
Subsequence Checks with Tie Breaking
How it works
A dictionary word can be formed by deletion exactly when it is a subsequence of the input. Scan the input with a pointer into each candidate word. Among matched words, prefer the longest, then the lexicographically smallest on equal length.
Steps
- Check each dictionary word as a subsequence.
- Compare its length with the best matched word.
- Use lexical order to break equal-length ties.
Complexity
- Time: O(dn + L) for d words, input length n, and dictionary characters L.
- Space: O(1) auxiliary space, excluding the returned word.
Things to watch for
- Characters must retain order.
- The lexical tie rule is required.
- Return an empty string if no word is a subsequence.
Python code example
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
C++ code example
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();
};
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.