สมมติว่าเรามีพจนานุกรมสตริงและสตริง เราต้องหาสตริงที่ยาวที่สุดในพจนานุกรมที่สามารถเกิดขึ้นได้โดยการลบอักขระบางตัวของสตริงที่กำหนด หากมีผลลัพธ์ที่เป็นไปได้มากกว่าหนึ่งรายการ ให้ส่งคืนคำที่ยาวที่สุดด้วยลำดับพจนานุกรมที่เล็กที่สุด หากไม่มีผลลัพธ์ ให้ส่งคืนสตริงว่าง ดังนั้นหากอินพุตเป็น "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
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ans :=สตริงว่าง
- สำหรับ i ในช่วง 0 ถึงขนาด d – 1
- x :=d[i]
- ถ้าขนาดของ x> ขนาดของ ans หรือ ขนาดของ x =ขนาดของ ans และ x
- ถ้า isSubsequence(s, x) เป็นจริง ให้ตอบ :=x
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
