Leetcode 848 Shifting Letters

发表于 |

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 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

分析：

  1. 题目定义了一个shift函数，将字母按照字母表顺序转换到下一个字母，’z’后又是’a’；题目给了一个shift数组，shift[i]代表要对前i+1个字母作shift[i]次shift函数操作。
  2. 注意数据长度达到20000，显然n^2的方法不可行，数据本身大小达到10^9，说明处理必须一步到位。

思路：
建立一个字典使0到25和zabc…xy互相对应，那么我们分析一个字符的时候便可以转换成数字来处理，处理结束后又可转换成字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
index = 0
d = {}
for s in 'zabcdefghijklmnopqrstuvwxy':
	d[s] = index
	d[index] = s
	index += 1

def shiftingLetters(S, shifts):
	# 因为每次都是对前i+1个字符进行操作，所以实际第一个字符被处理了sum(shift)，依次类推
	for i in range(len(shifts)-2,-1,-1):
		shifts[i] += shifts[i+1]
	res = []
	# S.length = shifts.length
	for i in range(len(S)):
		index = (d[S[i]] + shifts[i]) % 26
		res.append(d[index])
	return ''.join(res)