การเลื่อนตัวอักษร (Shifting Letters) ใน C++

ได้รับสตริง S และอาร์เรย์ shifts โดย shifts[i] = x หมายถึงเลื่อนตัวอักษร i+1 ตัวแรก x ครั้ง (z เลื่อนเป็น a) หาสตริงผลลัพธ์หลังเลื่อนทั้งหมด

ตัวอย่าง

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

คำอธิบาย − 1. เลื่อน 1 ตัวแรก 3: "dbc" 2. เลื่อน 2 ตัวแรก 5: "igc" 3. เลื่อน 3 ตัวแรก 9: "rpl"

แนวทางการแก้ปัญหา (Prefix Sum จากท้าย)

• คำนวณ prefix sum จากขวาไปซ้าย: shifts[i] += shifts[i+1] mod 26
• จากนั้นเลื่อนแต่ละตัวอักษร S[i] ตาม shifts[i] ที่คำนวณได้
• สูตร: new_char = (S[i] - 'a' + shifts[i]) % 26 + 'a'

ตัวอย่างโค้ด C++

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

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

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

ผลลัพธ์

rpl