Ma trận ký tự mở rộng bằng nhân với tập {a, b, c, d}. Kích thước nhân đôi mỗi lần. Cho chuỗi ký tự tại vị trí (i, j), tìm chuỗi tại (i, (j - N - 1) % N) (phần tử bên trái, xem ma trận như vòng tròn). Ví dụ:
Input: abb Output: aba Input: aadc Output: aacd Input: abbcd Output: abbcc
Cách hiệu quả: Nhận diện quy luật
Duyệt chuỗi từ cuối về đầu:
- Gặp
'b'hoặc'd'→ đổi thành'a'hoặc'c'và dừng. - Gặp
'a'hoặc'c'→ đổi thành'b'hoặc'd'và tiếp tục sang ký tự trước.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main() {
string seq = "abbcd";
int n = seq.length();
for (int i = n - 1; i >= 0; i--) {
if (seq[i] == 'b') { seq[i] = 'a'; break; }
if (seq[i] == 'd') { seq[i] = 'c'; break; }
if (seq[i] == 'a') seq[i] = 'b';
else if (seq[i] == 'c') seq[i] = 'd';
}
cout << "The Previous sequence is: " << seq;
return 0;
}
Kết quả
The previous sequence is: abbcc
Kết luận
Giải quyết tìm phần tử trước trong ma trận mở rộng bằng quy luật biến đổi ký tự. Code C++ ngắn gọn O(độ dài chuỗi).