資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學透過刪除在 C++ 中查詢字典中最長的單詞
假設我們有一個字串和一個字串字典，我們需要找到字典中最長的字串，該字串可以透過刪除給定字串的一些字元來形成。如果有多個可能的答案，則只需返回字典序最小的最長單詞。如果沒有結果，則返回空字串。因此，如果輸入類似於“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
- 在主方法中，執行以下操作：
- ans := 空字串
- 對於 i 從 0 到 d 的大小 – 1
- x := d[i]
- 如果 x 的大小 > ans 的大小，或者 x 的大小 = ans 的大小並且 x < ans，則
- 如果 isSubsequence(s, x) 為 true，則 ans := x
- 返回 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
更新於：2020年5月2日
152 次檢視
廣告