[leetcode #848] Shifting Letters


Problem


You are given a string s of lowercase English letters and an integer array shifts of the same length.
Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').
For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.
Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.
Return the final string after all such shifts to s are applied.
Example 1:
Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.
Example 2:
Input: s = "aaa", shifts = [1,2,3]
Output: "gfd"
Constraints:
・ 1 <= s.length <= 10⁵
・ s consists of lowercase English letters.
・ shifts.length == s.length
・ 0 <= shifts[i] <= 10⁹

Idea


問題は、所定のシフト値に基づいて、所定の文字列の各アルファベット文字をシフトすることである.逆に、シフトインデックスよりも小さいすべてのインデックスの文字をシフトする必要があります.したがって、後でrunningSum配列を作成し、runningSumの値に従ってinputの各文字を移動します.
アルゴリズムは以下の通りです.
  • シフト配列のrunningsumを逆シーケンスで求めた.
  • inputは、所与の文字列sの各文字にrunningsum値を加えてシフトする.
  • shiftの文字列を返します.
  • Solution

    class Solution {
        public String shiftingLetters(String s, int[] shifts) {
    
            // 1. get running sum
            long[] runningSum = new long[shifts.length];
            long sum = 0;
            for (int i=shifts.length-1; i >= 0; i--) {
                sum += shifts[i];
                runningSum[i] = sum;
            }
    
    	// 2. transform long to char
            StringBuilder sb = new StringBuilder();
            for (int i=0; i < s.length(); i++) {
                sb.append((char)(((long) (s.charAt(i) - 'a') + runningSum[i]) % 26 + 'a'));
            }
    
            return sb.toString();
        }
    }
    悪くも悪くもない結果になった.

    Reference


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