Letter Shifting

There's a string S composed of lowercase letters, and an array of integers shifts. The next letter in the alphabet is called the shift of the original letter (because the alphabet is circular, z will become a). For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'. For each shifts[i] = x, we will shift the first i+1 letters in S x times. Return the resulting string after applying all these shifts to S.

Example

Input: S = "abc", shifts = [3,5,9] Output: "rpl" Explanation: We start with "abc". After shifting the 1st letter in S 3 times, we get "dbc". After shifting the first 2 letters in S 5 times, we get "igc". Finally, after shifting these 3 letters 9 times, we get the answer "rpl".

Solution

/**
 * @param {string} S
 * @param {number[]} shifts
 * @return {string}
 */
var shiftingLetters = function(S, shifts) {
    var sub = 0;
    var base = "a".charCodeAt(0);
    var target = "";
    for(let i=S.length-1; i>=0; --i){
        sub = (sub + shifts[i]);
        let charPath = (S[i].charCodeAt(0) - base + sub) % 26;
        target = String.fromCharCode(base + charPath) + target;
        
    }
    return target;
};

Idea

This is a circular shifting problem for characters. You can calculate the number of shifts for each character based on the shifts array. The i-th letter should be shifted shifts[i] + shifts[i+1] + ... + shifts[shifts.length - 1] times. Although you can calculate the shifting length for each character directly using the array, it is easier to record the accumulated value from the end of the array and then perform circular shifting. Firstly, define a counter for the accumulated value sub, and Js does not have a char basic data type, so character operations need to be calculated using ASCII codes. Define base as the ASCII value of the character a, and target is the target string to be returned. Then, traverse the array from back to front, accumulate sub, calculate the ASCII value of the current character considering the added value, deduct the ASCII value of a, and then obtain the remaining length with respect to the character a. Finally, convert the ASCII value to character and concatenate it to the target string.

Daily Exercise

https://github.com/WindrunnerMax/EveryDay

Problem Source

https://leetcode-cn.com/problems/shifting-letters