Leetcode 848. Shifting Letters
Problem Explanation:
You have been given a string consisting of lowercase letters and an integer array of the same length as the string. In this problem, we need to perform shifts on the characters of the string using the integer values from the array.
The shifting operation is defined as moving the character along the alphabets by a certain number. For example, if we shift the character 'a' by 1, we get 'b', if we shift 'c' by 2, we get 'e' and so on. If we reach 'z' and still have shifts left, we wrap around to the start of the alphabet. So, 'z' shifted by 1 gives 'a'.
Now, the shifting operations are as follows: For each i in the array, we will shift the first i+1 letters of the string by the value of shifts[i].
At the end of all these shifting operations, we need to return the final string.
Let's take an example:
S = "abc", shifts = [3,5,9]
First, we shift the first letter 'a' by 3, yielding 'dbc'.
Next, we shift the first 2 letters 'd' and 'b' by 5, yielding 'igc'.
Finally, we shift the first 3 letters 'i', 'g', and 'c' by 9, yielding 'rpl'.
Thus, our final string after all shifts is "rpl".
Solution Approach:
This problem can be solved using cumulative sum in reverse order.
First, we iterate from the back of the shifts array, and for each position, we calculate the cumulative sum of the shifts. Since shifts can be very large, we reduce each sum to mod 26.
Then, we iterate over the string and for each character, we add the corresponding shift value to it, modulo 26. This value is added to the ASCII value of 'a' to get the shifted character.
C++ Solution
1
2c++
3class Solution {
4 public:
5 string shiftingLetters(string s, vector<int>& shifts) {
6 // Store the result
7 string result;
8
9 // Calculate the cumulative sum of shifts from the back
10 for (int i = shifts.size() - 2; i >= 0; --i)
11 shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
12
13 // Apply the shifts to the string
14 for (int i = 0; i < s.length(); ++i)
15 result += (s[i] - 'a' + shifts[i]) % 26 + 'a';
16
17 return result;
18 }
19};
Python Solution
1 2python 3class Solution: 4 def shiftingLetters(self, s: str, shifts: List[int]) -> str: 5 # Calculate the cumulative sum of shifts from the back 6 for i in range(len(shifts) - 2, -1, -1): 7 shifts[i] = (shifts[i] + shifts[i + 1]) % 26 8 9 # Apply the shifts to the string 10 return "".join(chr((ord(c) - ord('a') + shifts[i]) % 26 + ord('a')) for i, c in enumerate(s))
Java Solution
1 2java 3class Solution { 4 public String shiftingLetters(String s, int[] shifts) { 5 for (int i = shifts.length - 2; i >= 0; --i) 6 shifts[i] = (shifts[i] + shifts[i + 1]) % 26; 7 8 char[] chars = s.toCharArray(); 9 for (int i = 0; i < chars.length; ++i) 10 chars[i] = (char)((chars[i] - 'a' + shifts[i]) % 26 + 'a'); 11 12 return new String(chars); 13 } 14}
JavaScript Solution
1 2javascript 3var shiftingLetters = function(s, shifts) { 4 for (let i = shifts.length - 2; i >= 0; --i) 5 shifts[i] = (shifts[i] + shifts[i + 1]) % 26; 6 7 let res = ''; 8 for (let i = 0; i < s.length; ++i) 9 res += String.fromCharCode((s.charCodeAt(i) - 97 + shifts[i]) % 26 + 97); 10 11 return res; 12};
C# Solution
1 2csharp 3public class Solution { 4 public string ShiftingLetters(string s, int[] shifts) { 5 for (int i = shifts.Length - 2; i >= 0; --i) 6 shifts[i] = (shifts[i] + shifts[i + 1]) % 26; 7 8 var chars = s.ToCharArray(); 9 for (int i = 0; i < chars.Length; ++i) 10 chars[i] = (char)((chars[i] - 'a' + shifts[i]) % 26 + 'a'); 11 12 return new string(chars); 13 } 14}
PHP Solution
1
2php
3class Solution {
4
5 /**
6 * @param String $s
7 * @param Integer[] $shifts
8 * @return String
9 */
10 function shiftingLetters($s, $shifts) {
11 for ($i = count($shifts) - 2; $i >= 0; --$i)
12 $shifts[$i] = ($shifts[$i] + $shifts[$i + 1]) % 26;
13
14 $res = '';
15 for ($i = 0; $i < strlen($s); ++$i)
16 $res .= chr((ord($s[$i]) - 97 + $shifts[$i]) % 26 + 97);
17
18 return $res;
19 }
20}
Kotlin Solution
1 2kotlin 3class Solution { 4 fun shiftingLetters(s: String, shifts: IntArray): String { 5 for (i in shifts.size - 2 downTo 0) 6 shifts[i] = (shifts[i] + shifts[i + 1]) % 26 7 8 var res = "" 9 for (i in s.indices) 10 res += ((s[i] - 'a' + shifts[i]) % 26 + 'a'.toInt()).toChar() 11 12 return res 13 } 14}
Swift Solution
1 2swift 3class Solution { 4 func shiftingLetters(_ s: String, _ shifts: [Int]) -> String { 5 var shifts = shifts 6 for i in stride(from: shifts.count - 2, through: 0, by: -1) { 7 shifts[i] = (shifts[i] + shifts[i + 1]) % 26 8 } 9 10 var res = "" 11 let ascii_a = Int("a".unicodeScalars.first!.value) 12 for (i, c) in s.enumerated() { 13 let ascii_c = Int(c.unicodeScalars.first!.value) 14 let shift = (ascii_c - ascii_a + shifts[i]) % 26 + ascii_a 15 res.append(String(UnicodeScalar(shift)!)) 16 } 17 18 return res 19 } 20}
Summary
Whether it's with a high-level language like Python or a low-level language like C++, the essence of the solution remains consistent among the variety of programming languages: calculating the cumulative sum in reverse order first, then applying the corresponding shifts to the string characters. All solutions demonstrated here achieve the same result, although the way of achieving the same may differ based on the language's syntax and available built-in methods or functions.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.