Shifting Letters(Array,String,Prefix Sum)

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

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 <= 105
• s consists of lowercase English letters.
• shifts.length == s.length
• 0 <= shifts[i] <= 109

하나 더 풀어보는 leetcode 문제

 

핵조잡하다. Python, ord/chr 이라는 python에서 알파벳과 그 순서를 나타내는 Method를 이용해서 풀었다.

뭔가 Python 특화된 문제로 보여짐

 

1. Python

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        n = len(shifts)
        prefix = [shifts[-1]] * n
        for i in range(n-2,-1,-1):
            prefix[i] = prefix[i+1] + shifts[i]
        for i in range(n):
            prefix[i] %= 26
        ans = ""
        for i in range(len(s)):
            if ord(s[i]) + prefix[i] <= 122 :
                ans += chr(ord(s[i])+prefix[i])
            else :
                ans += chr(97+ord(s[i])+prefix[i]-123)
        return ans

 

 

2. .C++

 

C++도 비슷하다. 122, 96이라는 숫자가 원래 있는가보다.

String을 index 통해서 바꿀 수가 있고,

Char에 숫자를 더하면 숫자로 대소관계 계산될 땐 숫자로 자동 번역? 되고

Char로 계산될 땐 Char로 자동 번역? 된다.

 

즉, 알아서 맞춤형으로 Data type을 설정해준다. 고마운 녀석

 

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

        for(int j=0;j<n;j++){
            if(s[j]+shifts[j] <= 122){
                s[j] += shifts[j];
            }
            else{
                s[j] = 97 + s[j] + shifts[j] - 123;
            }
        }
        return s;

    }
};