Giả sử chúng ta có một danh sách các từ. Bây giờ hãy xem xét một trò chơi ma mà hai người chơi có thể tham gia vào nó. Ở đây người chơi thay thế các chữ cái nối nhau vào một chuỗi. Và chuỗi đang được thực hiện phải là tiền tố hợp lệ của một từ trong danh sách, và người chơi đánh vần bất kỳ từ nào trong danh sách sẽ bị thua. Chúng tôi phải kiểm tra xem người chơi đầu tiên có thể thắng hay không nếu cả hai người chơi đều chơi tối ưu.
Vì vậy, nếu đầu vào giống như words =["management", "manager", "min"], thì đầu ra sẽ là True, vì chúng có thể chơi như -
- m [Người chơi 1]
- ma [Người chơi 2]
- người đàn ông [Người chơi 1]
- năng lượng [Người chơi 2]
- manag [Người chơi 1]
- quản lý [Người chơi 2] thua
Vì vậy, người chơi 1 sẽ thắng.
Để 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 bản đồ mp
- đối với mỗi từ nó trong các từ, hãy thực hiện
- ch:=it [0]
- chèn nó vào mp [ch]
- mn:=inf
- đối với mỗi cặp khóa-giá trị trong mp, hãy thực hiện
- str:=giá trị của nó
- size:=kích thước của str
- nếu kích thước mod 2 giống 0, thì -
- trả lại 1
- trả về 0
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<string> &words) {
map<char, set<string>> mp;
for (auto &it : words) {
char ch = it[0];
mp[ch].insert(it);
}
int mn = INT_MAX;
for (auto &it : mp) {
string str = *(it.second.begin());
int size = str.size();
if (size % 2 == 0)
return 1;
}
return 0;
}
int main(){
vector<string> v = {"manage", "manager", "min"};
cout << solve(v);
} Đầu vào
{"manage", "manager", "min"} Đầu ra
1