1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String shiftingLetters(String s, int[] shifts) {
long[] totalShifts = new long[shifts.length];
long sum = 0;
for (int i = shifts.length - 1; i >= 0; i--) {
sum += shifts[i];
totalShifts[i] = sum;
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
int currShift = (int) (totalShifts[i] % 26);
int newCharAscii = s.charAt(i) + currShift;
char newChar = newCharAscii <= 122 ? (char) newCharAscii : (char) (96 + newCharAscii % 122);
ans.append(newChar);
}
return ans.toString();
}
}
|
这是我的第一次自己尝试. postfix sum.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public String shiftingLetters(String s, int[] shifts) {
for (int i = shifts.length - 2; i >= 0; i--) {
shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
ans.append((char) ((s.charAt(i) - 'a' + shifts[i]) % 26 + 'a'));
}
return ans.toString();
}
}
|
这个是Lee哥的答案. 就是在原数组上进行postfix sum, 边走边向26取余.
关于wrap的问题, 也得到了很好的解决, 先算出到a的offset, 然后加上shift, 最后再向26取余数, 然后在加上’a‘即可.
时间复杂度: O(n)
空间复杂度: O(n)
