Giả sử ta có một chuỗi, ta có thể tạo dãy con (subsequence) của chuỗi đó bằng cách xóa một số ký tự (có thể không xóa). Cho hai chuỗi source và target, ta phải tìm số lượng dãy con tối thiểu của source sao cho nối chúng lại bằng target. Nếu không thể, trả về -1. Ví dụ: source "abc", target "abcbc", kết quả 2.
Để giải quyết, ta thực hiện các bước sau:
Định nghĩa hàm possible nhận s và t.
Tạo map m.
Với mỗi ký tự c trong s, đánh dấu m[c] := 1.
Với mỗi ký tự c trong t, nếu m[c] bằng 0, trả về false.
Trả về true.
Từ phương thức main:
ssz := kích thước s, tsz := kích thước t.
Tạo map m với khóa kiểu char và giá trị kiểu mảng.
Với i từ 0 đến ssz: chèn i vào m[s[i]].
pre := -1, ret := 1.
Với i từ 0 đến tsz:
Nếu t[i] không có trong m, trả về -1.
v := m[t[i]].
Đặt i := chỉ số phần tử trong v lớn hơn pre (upper_bound).
Nếu i không phải cuối danh sách:
Tăng ret lên 1 và pre := v[0].
Ngược lại pre := v[i].
Trả về ret.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#include <bits/stdc++.h> using namespace std; class Solution { public: bool possible(string s, string t){ map <char, int> m; for(int i = 0; i < s.size(); i++){ m[s[i]] = 1; } for(int i = 0; i < t.size(); i++){ if(!m[t[i]])return false; } return true; } int shortestWay(string s, string t) { int ssz = s.size(); int tsz = t.size(); map <char, vector <int> > m; for(int i = 0; i < ssz; i++){ m[s[i]].push_back(i); } int pre = -1; int ret = 1; for(int i = 0; i < tsz; i++){ if(!m.count(t[i]))return -1; vector <int>& v = m[t[i]]; vector <int> :: iterator it = upper_bound(v.begin(), v.end(), pre); if(it == v.end()){ ret++; pre = v[0]; }else{ pre = *it; } } return ret; } }; main(){ Solution ob; cout << (ob.shortestWay("abc", "abcbc")); }Đầu vào
"abc" "abcbc"
Kết quả
2