Từ dài nhất trong từ điển thông qua xóa trong C ++

Giả sử chúng ta có một chuỗi và một từ điển chuỗi, chúng ta phải tìm chuỗi dài nhất trong từ điển có thể được hình thành bằng cách xóa một số ký tự của chuỗi đã cho. Nếu có nhiều hơn một kết quả có thể xảy ra, thì chỉ cần trả về từ dài nhất có thứ tự từ vựng nhỏ nhất. Nếu không có kết quả, thì trả về một chuỗi trống. Vì vậy, nếu đầu vào là “abpcplea” và d =[“ale”, “apple”, “khỉ”, “plea”], thì kết quả sẽ là “apple”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là isSubsequence (). Điều này sẽ mất s1 và s2
• j:=0
• cho tôi trong phạm vi từ 0 đến kích thước của s1
  • nếu s2 [j] =s1 [i], thì hãy tăng j lên 1
  • nếu j =kích thước của s2, thì ngắt vòng lặp
• trả về true nếu j =kích thước của s2
• Từ phương pháp chính, hãy thực hiện như sau -
• ans:=một chuỗi trống
• cho tôi trong phạm vi từ 0 đến kích thước là d - 1
  • x:=d [i]
  • nếu kích thước của x> kích thước của ans hoặc kích thước của x =kích thước của ans và x
  • nếu isSubsequence (s, x) là true, thì ans:=x

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

"abpcplea"
["ale","apple","monkey","plea"]

Đầu ra

apple