![[Bài 48] Bài Toán Tần Suất Ký Tự Trong Xâu](/storage/photos/1/cpp/dem-tan-suat-ky-tu-trong-xau.png "[Bài 48] Bài Toán Tần Suất Ký Tự Trong Xâu")
Đếm tần suất ký tự trong xâu và các bài toán liên quan tới sự xuất hiện của ký tự trong xâu các bạn có thể sử dụng mảng đánh dấu hoặc map. Trong bài viết này mình sẽ hướng dẫn các bạn dạng bài tập này và một vài bài tập ví dụ minh họa.
1. Đếm tần suất ký tự bằng mảng đánh dấu
Để đếm xem mỗi ký tự trong xâu xuất hiện bao nhiêu lần bạn có thể sử dụng kỹ thuật mảng đánh dấu, nếu bạn chưa biết kỹ thuật này có thể tham khảo tại đây
Ý tưởng là mình sẽ sử dụng mã ASCII của các ký tự để đếm tần suất tương ứng của ký tự đó, các ký tự trong bảng mã ASCII có thứ tự từ 0 tới 255 nên bạn chỉ cần sử dụng một mảng đánh dấu có 256 phần tử là có thể đếm được tần suất.
Ví dụ khi gặp kí tự 'a' trong xâu ký tự thì bạn sẽ đếm tần suất của nó thông qua phần tử có chỉ số 97 của mảng đánh dấu, vì 'a' có mã ASCII là 97
Sau khi bạn tìm được tần suất của từng ký tự bạn có thể triển khai nhiều bài toán mở rộng khác.
Độ phức tạp : O(N)
Mã nguồn :
#include <string>
using namespace std;
int main(){
string s = "azbook azbook aaa";
int cnt[256] = {0};
for (int i = 0; i < s.size(); i++) {
cnt[s[i]]++;
}
for (int i = 0; i < 256; i++) {
if (cnt[i] != 0) {
cout << (char)i << " xuat hien " << cnt[i] << "lan\n";
}
}
}
Output :
a xuat hien 5lan
b xuat hien 2lan
k xuat hien 2lan
o xuat hien 4lan
z xuat hien 2lan
2. Đếm tần suất ký tự bằng map
Ngoài cách sử dụng mảng đánh dấu bạn có thể sử dụng map, nếu bạn chưa biết cách dùng map thì có thể tham khảo tại blog của mình bài viết về map nhé.
Ý tưởng là mình sẽ dùng một map<char,int> trong đó key của map sẽ lưu ký tự và value sẽ lưu tần suất tương ứng.
Cách này thì ngắn gọn tuy nhiên độ phức tạp tệ hơn so với mảng đánh dấu
Độ phức tạp : O(NlogN)
Mã nguồn :
#include <string>
#include <map>
using namespace std;
int main(){
string s = "azbook AZBook aaa";
map<char, int> mp;
for (int i = 0; i < s.size(); i++) {
mp[s[i]]++;
}
for (pair<char, int> it : mp) {
cout << it.first << " xuat hien " << it.second << " lan\n";
}
}
Output :
A xuat hien 1 lan
B xuat hien 1 lan
Z xuat hien 1 lan
a xuat hien 4 lan
b xuat hien 1 lan
k xuat hien 2 lan
o xuat hien 4 lan
z xuat hien 1 lan
3. Bài tập áp dụng
Bài tập 1 : Đếm số lượng ký tự khác nhau trong xâu
Bài này mình sẽ sử dụng mảng đánh dấu để đánh dấu sự xuất hiện của ký tự trong xâu sau đó đếm số lần xuất hiện của các ký tự khác nhau.
#include <string>
#include <map>
using namespace std;
int main(){
string s = "azbook AZbook aaa";
int cnt[256] = {0};
for (int i = 0; i < s.size(); i++) {
cnt[s[i]] = 1;
}
int dem = 0;
for (int i = 0; i < 256; i++) {
dem += cnt[i];
}
cout << "So luong ki tu khac nhau : " << dem << endl;
}
Output :
Bài tập 2 : Liệt kê các ký tự trong xâu và tần suất của nó theo thứ tự xuất hiện trong xâu
Trong mục 1 mình đã hướng dẫn các bạn cách duyệt theo thứ tự từ điển abc, nếu yêu cầu duyệt theo thứ tự xuất hiện trong xâu thì bạn duyệt xâu và in ra tần suất tương ứng.
Để tránh việc in 1 ký tự nhiều lần thì bạn sẽ cho tần suất của nó về 0 sau khi đã in trước đó.
#include <string>
#include <map>
using namespace std;
int main(){
string s = "azbook AZbook aaa";
int cnt[256] = {0};
for (int i = 0; i < s.size(); i++) {
cnt[s[i]]++;
}
for (int i = 0; i < s.size(); i++) {
if (cnt[s[i]] != 0) {
cout << s[i] << " xuat hien " << cnt[s[i]] << " lan\n";
// Lan sau gap s[i] se ko in nua
cnt[s[i]] = 0;
}
}
}
Output :
z xuat hien 1 lan
b xuat hien 1 lan
o xuat hien 4 lan
k xuat hien 2 lan
xuat hien 2 lan
A xuat hien 1 lan
Z xuat hien 1 lan
B xuat hien 1 lan
Bài tập 3 : Kiểm tra xâu pangram
Xâu pangram là xâu mà chứa đầy đủ tất cả các chữ cái từ a tới z không phân biệt hoa thường.
#include <string>
#include <ctype.h>
using namespace std;
int main(){
string s = "azbookABCDefghijklmnopqrstuvWXYZ";
int cnt[256] = {0};
for (int i = 0; i < s.size(); i++) {
cnt[tolower(s[i])]++;
}
bool ok = true;
for (int i = 'a'; i <= 'z'; i++) {
if (cnt[i] == 0) {
ok = false; break;
}
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}
Output :
