【差分数组】字母移位 II

题目

6158. 字母移位 II

---

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

示例 1：

输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
输出："ace"
解释：首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。
然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。
最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。

示例 2:

输入：s = "dztz", shifts = [[0,0,0],[1,1,1]]
输出："catz"
解释：首先，将下标从 0 到 0 的字母向前移位，得到 s = "cztz" 。
最后，将下标从 1 到 1 的字符向后移位，得到 s = "catz" 。

提示：

• 1 <= s.length, shifts.length <= 5 * 10^4
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s 只包含小写英文字母。

解题

方法一：差分数组

思路

首先维护一个长为 s.length() + 1 的差分数组(diffs)，遍历移位数组，对于 shift[i]：

• 如果当前区间为向后移位(shift[i][2] == 1)，那么就是在 shift[i][0] ~ shift[i][1] 上增量，所以 diffs[shift[i][0]] 自增，diffs[shift[i][1] + 1] 自减。
• 如果当前区间为向前移位(shift[i][2] == 0)，那么就是在 shift[i][0] ~ shift[i][1] 上减量，所以 diffs[shift[i][0]] 自减，diffs[shift[i][1] + 1] 自增。

遍历完成后差分数组就维护好了，随后遍历字符串，对于每一个字符：

首先维护变化量(diff)，然后把该字符移位 diff。

注意：chs[i] = (char) (((curr + diff) % 26 + 26) % 26 + 'a') 这里第一次余 26 把变化后的字符所代表的数字限制在了$[-25, 25]$ ，然后加上 26 再余 26 就限制在了 $[0, 25]$ ，随后就可以把它加上字符 'a' 放回原字串中了。

代码

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int n = s.length();
        int[] diffs = new int[n + 1];
        for (int[] shift : shifts) {
            if (shift[2] == 1) {
                ++diffs[shift[0]];
                --diffs[shift[1] + 1];
            } else {
                --diffs[shift[0]];
                ++diffs[shift[1] + 1];
            }
        }
        char[] chs = s.toCharArray();
        for (int i = 0, diff = 0; i < n; ++i) {
            int curr = chs[i] - 'a';
            diff += diffs[i];
            chs[i] = (char) (((curr + diff) % 26 + 26) % 26 + 'a');
        }
        return String.valueOf(chs);
    }
}

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.length();
        vector<int> diffs(n + 1);
        for (auto& shift : shifts) {
            if (shift[2]) {
                ++diffs[shift[0]];
                --diffs[shift[1] + 1];
            } else {
                --diffs[shift[0]];
                ++diffs[shift[1] + 1];
            }
        }
        for (int i = 0, diff = 0; i < n; ++i) {
            int curr = s[i] - 'a';
            diff += diffs[i];
            s[i] = ((curr + diff) % 26 + 26) % 26 + 'a';
        }
        return s;
    }
};