LeetCode 1048
Xem dạng PDF
Gửi bài giải
Điểm:
999 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig
Nhanbin, một người cực kỳ đam mê... biến hóa từ ngữ. Một ngày nọ, nó nghĩ ra một trò chơi: cho một danh sách các từ toàn là chữ cái thường (a-z), bạn phải nối các từ đó lại thành một chuỗi sao cho từ sau chỉ khác từ trước đúng 1 chữ cái, bằng cách thêm 1 chữ vào bất kỳ vị trí nào, nhưng không được xáo trộn thứ tự các chữ còn lại.
Ví dụ:
- Từ a có thể lên level thành ab hoặc ba hoặc za, miễn là chỉ thêm 1 chữ cái vào bất kỳ đâu mà không thay đổi thứ tự ban đầu.
- Nhưng từ abc không lên được cab vì đổi thứ tự là chịu chết.
- Mỗi lần lên một từ mới như vậy, Nhanbin gọi đó là level-up.
Giờ nhiệm vụ của bạn là:
👉 Tìm chuỗi level-up dài nhất có thể trong danh sách các từ mà Nhanbin đưa.
~\texttt{Input}~
Dòng đầu tiên là một số nguyên n (~1 \leq n \leq 10 ^ 3~) — số lượng từ trong danh sách.
~n~ dòng tiếp theo mỗi dòng chứa một từ chỉ gồm các chữ cái thường trong bảng chữ cái tiếng Anh (a–z), độ dài từ không vượt quá 16.
~\texttt{Output}~
- Một dòng duy nhất là độ dài của chuỗi level-up dài nhất có thể tạo được từ danh sách các từ đã cho.
Sample Input 1
6
bda
a
b
bca
ba
bdca
Sample Output 1
4
Bình luận
Code:
include <bits/stdc++.h>
using namespace std; int main() { int n; cin >> n; vector<string> a(n); for(int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end(), { return x.size() < y.size(); }); unordered_map<string, int> dp; int ans = 1; for(auto &s : a){ dp[s] = 1; for(int i = 0; i < s.size(); i++){ string t = s.substr(0, i) + s.substr(i+1); if(dp.count(t)){ dp[s] = max(dp[s], dp[t] + 1); } } ans = max(ans, dp[s]); } cout << ans << ‘\n’; }