Dịch chuyển ký tự (Shifting Letters) C++

Cho chuỗi S chữ thường và mảng shifts. shifts[i] = x nghĩa là dịch chuyển i+1 ký tự đầu tiên của S lần lượt x lần (z → a). Tìm chuỗi cuối cùng.

Ví dụ

Input - S = "abc", shifts = [3,5,9] Output - "rpl"

Giải thích - Shift 1 ký tự 3 lần: "dbc". Shift 2 ký tự 5 lần: "igc". Shift 3 ký tự 9 lần: "rpl".

Phương pháp tiếp cận (Tối ưu O(n))

• Tính tích lũy shifts từ phải sang trái: shifts[i] += shifts[i+1], modulo 26
• Áp dụng cho từng ký tự: S[i] = (S[i] - 'a' + shifts[i]) % 26 + 'a'

Ví dụ code C++

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

class Solution {
public:
    string shiftingLetters(string S, vector<int>& shifts) {
        for (int i = shifts.size() - 2; i >= 0; i--) {
            shifts[i] += shifts[i + 1];
            shifts[i] %= 26;
        }
        for (int i = 0; i < S.size(); i++) {
            S[i] = ((S[i] - 'a') + shifts[i]) % 26 + 'a';
        }
        return S;
    }
};

int main() {
    vector<int> v = {3, 5, 9};
    Solution ob;
    cout << ob.shiftingLetters("abc", v);
    return 0;
}

Kết quả

rpl