class Solution {
public:
string shiftingLetters(string s, vector<int>& shifts) {
}
};
848. 字母移位
有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。
我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。
shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。
返回 将所有这些移位都应用到 s 后最终得到的字符串 。
示例 1：
输入：s = "abc", shifts = [3,5,9] 输出："rpl" 解释： 我们以 "abc" 开始。 将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。 再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。 最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。
示例 2:
输入: s = "aaa", shifts = [1,2,3] 输出: "gfd"
提示:
1 <= s.length <= 105s 由小写英文字母组成shifts.length == s.length0 <= shifts[i] <= 109原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-19 15:11:59
func shiftingLetters(S string, shifts []int) string {
l := len(shifts)
sum := 0
sBytes := []byte(S)
aASCII := int("a"[0])
for i := l - 1; i >= 0; i-- {
sum += shifts[i]
sBytes[i] = byte((int(sBytes[i])-aASCII+sum)%26 + aASCII)
}
return string(sBytes)
}
java 解法, 执行用时: 14 ms, 内存消耗: 53 MB, 提交时间: 2023-09-19 15:10:51
class Solution {
public String shiftingLetters(String S, int[] shifts) {
StringBuilder ans = new StringBuilder();
int X = 0;
for (int shift: shifts)
X = (X + shift) % 26;
for (int i = 0; i < S.length(); ++i) {
int index = S.charAt(i) - 'a';
ans.append((char) ((index + X) % 26 + 97));
X = Math.floorMod(X - shifts[i], 26);
}
return ans.toString();
}
}
cpp 解法, 执行用时: 112 ms, 内存消耗: 66.6 MB, 提交时间: 2023-09-19 15:10:27
class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
int size = (int)S.size();
int cnt = 0;
for (int i = size - 1; i >= 0;i--) {
cnt += shifts[i] % 26;
int index = S[i] - 'a' + cnt;
S[i] = (index % 26) + 'a';
}
return S;
}
};
python3 解法, 执行用时: 212 ms, 内存消耗: 26.7 MB, 提交时间: 2023-09-19 15:09:53
class Solution(object):
def shiftingLetters(self, S, shifts):
ans = []
X = sum(shifts) % 26
for i, c in enumerate(S):
index = ord(c) - ord('a')
ans.append(chr(ord('a') + (index + X) % 26))
X = (X - shifts[i]) % 26
return "".join(ans)
python3 解法, 执行用时: 148 ms, 内存消耗: 27.6 MB, 提交时间: 2023-09-19 15:08:35
class Solution:
def shiftingLetters(self, s: str, shifts: List[int]) -> str:
return ''.join(chr(97 + (ord(c) - 97 + i) % 26) for c, i in zip(s, list(accumulate(shifts[::-1]))[::-1]))
python3 解法, 执行用时: 232 ms, 内存消耗: 27.8 MB, 提交时间: 2023-09-19 15:07:48
'''
前缀数组
'''
class Solution:
def shiftingLetters(self, s: str, shifts: List[int]) -> str:
n = len(shifts)
presum = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
presum[i] += shifts[i] + presum[i+1]
return ''.join(self.changeLetter(c, presum[i]) for i, c in enumerate(s))
def changeLetter(self, c: str, n: int) -> str:
t = ord(c) + (n % 26)
if t > ord('z'):
return chr(t-26)
return chr(t)