通过C ++删除字典中最长的单词
假设我们有一个字符串和一个字符串字典，我们必须在字典中找到最长的字符串，该字符串可以通过删除给定字符串的某些字符来形成。如果有多个可能的结果，则仅以最小的字典顺序返回最长的单词。如果没有结果，则返回一个空白字符串。因此，如果输入类似于“abpcplea”，并且d=[“ale”，“apple”，“monkey”，“plea”]，则结果将为“apple”。
为了解决这个问题，我们将遵循以下步骤-
定义一个称为的方法isSubsequence()。这将需要s1和s2
j：=0
对于范围从0到s1的i
如果s2[j]=s1[i]，则将j增加1
如果j=s2的大小，则打破循环
如果j=s2的大小，则返回true
从主要方法中，执行以下操作-
ans：=一个空白字符串
对于范围从0到d–1的i
如果isSubsequence(s,x)为true，则ans：=x
x：=d[i]
如果x的大小>ans的大小或x的大小=ans的大小且x<ans的大小，则
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSubsequence(string s1, string s2){
int j =0;
for(int i = 0; i < s1.size(); i++){
if(s2[j] == s1[i]){
j++;
if(j == s2.size()) break;
}
}
return j == s2.size();
}
string findLongestWord(string s, vector<string>& d) {
string ans = "";
for(int i = 0; i < d.size(); i++){
string x = d[i];
if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){
if(isSubsequence(s, x)) ans = x;
}
}
return ans;
}
};
main(){
vector<string> v = {"ale","apple","monkey","plea"};
Solution ob;
cout << (ob.findLongestWord("abpcplea", v));
}输入值
"abpcplea" ["ale","apple","monkey","plea"]
输出结果
apple