Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/848.html

848. Shifting Letters

Level

Medium

Description

We have a string S of lowercase letters, and an integer array shifts.

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.

Note:

1. 1 <= S.length = shifts.length <= 20000
2. 0 <= shifts[i] <= 10 ^ 9

Solution

Calculate accumulative shifts for each index, from last to first. Since there are only 26 lowercase letters, the shifts should do modulo operation by 26. After accumulative shifts are calculated, do the accumulative shifts for each index.

• Java
• C++
• Python
• Go

• class Solution {
      public String shiftingLetters(String S, int[] shifts) {
          int length = shifts.length;
          shifts[length - 1] %= 26;
          for (int i = length - 2; i >= 0; i--)
              shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
          char[] array = S.toCharArray();
          for (int i = 0; i < length; i++) {
              int num = array[i] - 'a';
              num = (num + shifts[i]) % 26;
              array[i] = (char) (num + 'a');
          }
          return new String(array);
      }
  }
  

• // OJ: https://leetcode.com/problems/shifting-letters/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      string shiftingLetters(string s, vector<int>& A) {
          int shift = 0;
          for (int i = A.size() - 1; i >= 0; --i) {
              shift = (shift + A[i]) % 26;
              s[i] = (s[i] - 'a' + shift) % 26 + 'a';
          }
          return s;
      }
  };
  

• class Solution:
      def shiftingLetters(self, s: str, shifts: List[int]) -> str:
          n, t = len(s), 0
          s = list(s)
          for i in range(n - 1, -1, -1):
              t += shifts[i]
              j = (ord(s[i]) - ord('a') + t) % 26
              s[i] = ascii_lowercase[j]
          return ''.join(s)
  
  ############
  
  class Solution(object):
      def shiftingLetters(self, S, shifts):
          """
          :type S: str
          :type shifts: List[int]
          :rtype: str
          """
          _len = len(S)
          shifts_sum = sum(shifts)
          shifts_real = []
          for shift in shifts:
              shifts_real.append(shifts_sum)
              shifts_sum -= shift
          def shift_map(string, shift_time):
              shifted = ord(s) + (shift_time % 26)
              return chr(shifted if shifted <= ord('z') else shifted - 26)
          ans = ''
          for i, s in enumerate(S):
              ans += shift_map(s, shifts_real[i])
          return ans
  

• func shiftingLetters(s string, shifts []int) string {
  	t := 0
  	n := len(s)
  	cs := []byte(s)
  	for i := n - 1; i >= 0; i-- {
  		t += shifts[i]
  		j := (int(cs[i]-'a') + t) % 26
  		cs[i] = byte('a' + j)
  	}
  	return string(cs)
  }
  

All Problems

All Solutions