数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法律通过删除给定的 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
更新于： 2019 年 11 月 1 日
171 次浏览
广告