Đếm số từ mà ký tự thứ i là ký tự (i-1), i hoặc (i+1) của từ cho trước trong C++

Cho một chuỗi str[] làm đầu vào. Mục tiêu là đếm số lượng từ có cùng độ dài với str[] và thỏa mãn điều kiện: ký tự thứ i có thể được thay thế bằng ký tự tại vị trí (i-1), i hoặc (i+1).

Đối với ký tự đầu tiên, chỉ có thể thay thế bằng ký tự tại vị trí i hoặc i+1.
Đối với ký tự cuối cùng, chỉ có thể thay thế bằng ký tự tại vị trí i-1 hoặc i.

Ví dụ

Đầu vào − str[] = "TPP"

Đầu ra − Số lượng từ thỏa mãn: 4

Giải thích:

Thay T bằng T (i) hoặc P đầu tiên (i+1) = TPP, PPP
Thay P đầu tiên bằng T (i-1), P (i), hoặc P thứ 2 (i+1) = TTP, TPP, TPP
Thay P thứ 2 bằng P (i-1) hoặc P (i) = TPP, TPP
Các tổ hợp duy nhất: TPP, PPP, TTP, PTP

Đầu vào − str = "aaa"

Đầu ra − Số lượng từ thỏa mãn: 1

Giải thích:

Tất cả các thay thế đều cho kết quả "aaa"
Tổ hợp duy nhất: aaa

Phương pháp giải

Với mỗi ký tự, có 3 khả năng thay thế. Nếu ba ký tự (i-1), i, (i+1) đều khác nhau → 3 lựa chọn. Nếu hai ký tự trùng nhau → 2 lựa chọn. Nếu cả ba trùng nhau → 1 lựa chọn.

Duyệt qua chuỗi, kiểm tra tính duy nhất và nhân số lượng lựa chọn tương ứng. Với ký tự đầu và cuối, kiểm tra tương tự và nhân 2 hoặc 1.

• Nhận chuỗi str[] dưới dạng mảng ký tự.
• Hàm total(char str[], int length) trả về số lượng từ thỏa mãn.
• Khởi tạo count = 1 (tính luôn từ gốc).
• Nếu độ dài = 1, trả về 1.
• Kiểm tra ký tự đầu (index 0): nếu trùng ký tự thứ 2 thì nhân 1, ngược lại nhân 2.
• Duyệt từ ký tự thứ 2 đến ký tự倒数第二 (i=1 đến length-2):
  • Nếu str[i] trùng cả str[i-1] và str[i+1] → nhân 1.
  • Nếu trùng một trong hai → nhân 2.
  • Nếu str[i-1] == str[i+1] → nhân 2.
  • Ngược lại → nhân 3.
• Kiểm tra ký tự cuối: nếu trùng ký tự trước đó → nhân 1, ngược lại nhân 2.
• Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int total(char str[], int length) {
    int count = 1;
    if (length == 1) return count;
    if (str[0] == str[1]) count *= 1;
    else count *= 2;
    for (int j = 1; j < length - 1; j++) {
        if (str[j] == str[j-1] && str[j] == str[j+1]) count *= 1;
        else if (str[j] == str[j-1]) count *= 2;
        else if (str[j] == str[j+1]) count *= 2;
        else if (str[j-1] == str[j+1]) count *= 2;
        else count *= 3;
    }
    if (str[length - 1] == str[length - 2]) count *= 1;
    else count *= 2;
    return count;
}

int main() {
    char str[] = "TPP";
    int length = strlen(str);
    cout << "Count of words whose i-th letter is either (i-1)-th, i-th, or (i+1)-th letter of given word are: " << total(str, length) << endl;
    return 0;
}

Đầu ra

Count of words whose i-th letter is either (i-1)-th, i-th, or (i+1)-th letter of given word are: 4