C++ 中通过删除字符串找出字典中的最长单词
c++server side programmingprogramming
假设我们有一个字符串和一个字符串字典，我们需要找出通过删除给定字符串中的部分字符所能得到的最长字符串。如果结果不止一个，则返回字典顺序最小的最长单词。如果没有结果，则返回一个空字符串。因此，如果输入为 “abpcplea”，并且 d = [“ale”, “apple”, “monkey”, “plea”]，则结果为 “apple”。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为 isSubsequence() 的方法。这将需要 s1 和 s2
- j := 0
- i 的范围从 0 到 s1 的大小
- 如果 s2[j] = s1[i]，则将 j 加 1
- 如果 j = s2 的大小，则跳出循环
- 如果 j = s2 的大小，则返回 true
- 在 main 方法中，执行以下操作 −
- ans := 一个空字符串
- i 的范围从 0 到 d 的大小 – 1
- x := d[i]
- 如果 x 的大小 > ans 的大小 或 x 的大小 = ans 的大小且 x < ans，则
- 如果 isSubsequence(s, x) 为真，则 ans := x
- return 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
