Từ dài nhất trong từ điển bằng xóa ký tự (Longest Word in Dictionary through Deleting) trong C++

Cho chuỗi s và từ điển d. Tìm từ dài nhất trong d là dãy con của s (có thể xóa ký tự). Nếu nhiều từ cùng độ dài, lấy từ nhỏ nhất theo từ điển.

Ví dụ: s="abpcplea", d=["ale","apple","monkey","plea"] → "apple".

Thuật toán

1. Hàm kiểm tra isSubsequence(s, t): hai con trỏ duyệt s và t.
2. Duyệt từ điển, cập nhật kết quả nếu từ dài hơn hoặc cùng dài nhưng từ điển nhỏ hơn.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    bool isSubsequence(const string& s, const string& t) {
        int j=0;
        for (char c : s) if (c == t[j]) if (++j == t.size()) return true;
        return false;
    }
public:
    string findLongestWord(string s, vector& d) {
        string ans="";
        for (string& w : d) {
            if (w.size() > ans.size() || (w.size()==ans.size() && w < ans)) {
                if (isSubsequence(s, w)) ans = w;
            }
        }
        return ans;
    }
};

int main() {
    vector v = {"ale","apple","monkey","plea"};
    Solution ob;
    cout << ob.findLongestWord("abpcplea", v); // apple
    return 0;
}

Đầu vào / Đầu ra

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

Output: apple