Sponsored
Sponsored
This approach involves using a two-pointer technique to check if a string from the dictionary is a subsequence of the given string s. We iterate through each word in the dictionary and for each word, use two pointers to traverse through the word and s. If all characters of the word are found in the same order in s, then it's a valid word. We maintain a result variable to track the longest valid word found so far, and if multiple are of the same length, we track the smallest lexicographical order.
s. This is because we potentially traverse the entire string for each dictionary word.1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7bool isSubsequence(const string &s, const string &word) {
8 int i = 0, j = 0;
9 while (i < s.size() && j < word.size()) {
10 if (s[i] == word[j]) {
11 j++;
12 }
13 i++;
14 }
return j == word.size();
}
string findLongestWord(string s, vector<string>& dictionary) {
string result = "";
for (const string &word : dictionary) {
if (isSubsequence(s, word)) {
if (word.size() > result.size() || (word.size() == result.size() && word < result)) {
result = word;
}
}
}
return result;
}
int main() {
string s = "abpcplea";
vector<string> dictionary = {"ale", "apple", "monkey", "plea"};
cout << findLongestWord(s, dictionary) << endl;
return 0;
}This C++ implementation follows a similar logic as the C program, leveraging the string class and vector collection for handling words and storing the dictionary. The function isSubsequence is used to determine if a word can be formed by deleting some characters in s, and the main function iterates through the dictionary to find the longest valid word.
This approach involves sorting the dictionary by length (descending) and lexicographical order (ascending). By sorting first, you can ensure that you are checking the longest available words first while resolving ties based on the smallest alphabetical order. We then iterate through this sorted list and use a function to check if a word is a valid subsequence of s.
1def is_subsequence(s, word):
This Python implementation uses sorting to align words by the desirable evaluation order: first longest, then smallest lexicographically. The `is_subsequence` function checks if a word is a subsequence of `s`, as before accomplished using iterators for efficiency.