通过删除C ++中给定字符串的某些字符来查找字典中最大的单词
考虑我们有一个字典和一个字符串s。在字典中找到最长的字符串，可以通过删除字符串s的某些字符来形成。假设s为“apbreoigroakml”，则字典中有{“prog”，“ram”，“program”}，则结果为“program”。
为了解决这个问题，我们将遍历所有字典单词，对于每个单词，我们将检查给定字符串的子序列是否是所有此类单词中最长的。最后返回给定字符串的最长单词作为子序列。
示例
#include<iostream>
#include<vector>
using namespace std;
bool isSubSequence(string s1, string s2) {
int m = s1.length(), n = s2.length();
int j = 0;
for (int i=0; i<n&&j<m; i++)
if (s1[j] == s2[i])
j++;
return (j==m);
}
string getLongestSubstr(vector <string > dict, string s) {
string result = "";
int length = 0;
for (string word : dict) {
if (length < word.length() && isSubSequence(word, s)) {
result = word;
length = word.length();
}
}
return result;
}
int main() {
vector <string > dict = {"prog", "ram", "program"};
string str = "apbreoigroakml" ;
cout << getLongestSubstr(dict, str) << endl;
}输出结果
program
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短