資料結構
網路
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 次瀏覽
廣告