Medium

题目描述

给定一个由小写英文字母组成的字符串 s 和一个二维整数数组 shifts，其中 shifts[i] = [starti, endi, directioni]。对于每个 i，如果 directioni = 1，则将 s 中从索引 starti 到 endi（包含）的字符向前移位；如果 directioni = 0，则向后移位。

向前移位字符意味着用字母表中的下一个字母替换它（环绕，所以 ‘z’ 变成 ‘a’）。类似地，向后移位字符意味着用字母表中的前一个字母替换它（环绕，所以 ‘a’ 变成 ‘z’）。

返回应用所有移位操作后的最终字符串。

示例 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 由小写英文字母组成

解题思路

这道题考查的是区间更新和前缀和的应用。

核心思路： 直接按照题意对每个移位操作进行处理会导致时间复杂度过高。我们需要优化这个过程。

优化方法 - 差分数组：

  1. 使用差分数组记录每个位置的净移位次数
  2. 对于区间 [start, end]，如果 direction = 1（向前），在 start 位置 +1，在 end+1 位置 -1；如果 direction = 0（向后），在 start 位置 -1，在 end+1 位置 +1
  3. 通过前缀和还原每个位置的实际移位次数
  4. 对原字符串中的每个字符应用相应的移位

具体步骤：

  • 创建长度为 n+1 的差分数组 diff
  • 遍历所有移位操作，更新差分数组
  • 计算前缀和得到每个位置的净移位次数
  • 对字符串的每个字符应用移位，注意处理负数和模运算

这种方法将时间复杂度从 O(m×n) 优化到 O(m+n)，其中 m 是移位操作数，n 是字符串长度。

代码实现

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.length();
        vector<int> diff(n + 1, 0);
        
        // 构建差分数组
        for (const auto& shift : shifts) {
            int start = shift[0], end = shift[1], direction = shift[2];
            int delta = (direction == 1) ? 1 : -1;
            diff[start] += delta;
            diff[end + 1] -= delta;
        }
        
        // 计算前缀和得到每个位置的净移位次数
        int netShift = 0;
        for (int i = 0; i < n; i++) {
            netShift += diff[i];
            // 应用移位，处理负数情况
            int shift = ((netShift % 26) + 26) % 26;
            s[i] = 'a' + (s[i] - 'a' + shift) % 26;
        }
        
        return s;
    }
};

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        diff = [0] * (n + 1)
        
        # 构建差分数组
        for start, end, direction in shifts:
            delta = 1 if direction == 1 else -1
            diff[start] += delta
            diff[end + 1] -= delta
        
        # 计算前缀和并应用移位
        result = []
        net_shift = 0
        for i in range(n):
            net_shift += diff[i]
            # 处理负数情况
            shift = ((net_shift % 26) + 26) % 26
            new_char = chr(ord('a') + (ord(s[i]) - ord('a') + shift) % 26)
            result.append(new_char)
        
        return ''.join(result)

public class Solution {
    public string ShiftingLetters(string s, int[][] shifts) {
        int n = s.Length;
        int[] diff = new int[n + 1];
        
        // 构建差分数组
        foreach (var shift in shifts) {
            int start = shift[0], end = shift[1], direction = shift[2];
            int delta = direction == 1 ? 1 : -1;
            diff[start] += delta;
            diff[end + 1] -= delta;
        }
        
        // 计算前缀和并应用移位
        char[] result = s.ToCharArray();
        int netShift = 0;
        for (int i = 0; i < n; i++) {
            netShift += diff[i];
            // 处理负数情况
            int shift = ((netShift % 26) + 26) % 26;
            result[i] = (char)('a' + (result[i] - 'a' + shift) % 26);
        }
        
        return new string(result);
    }
}

var shiftingLetters = function(s, shifts) {
    const n = s.length;
    const diff = new Array(n + 1).fill(0);
    
    for (const [start, end, direction] of shifts) {
        const shift = direction === 1 ? 1 : -1;
        diff[start] += shift;
        diff[end + 1] -= shift;
    }
    
    let result = '';
    let currentShift = 0;
    
    for (let i = 0; i < n; i++) {
        currentShift += diff[i];
        const charCode = s.charCodeAt(i) - 97;
        const newCharCode = ((charCode + currentShift) % 26 + 26) % 26;
        result += String.fromCharCode(newCharCode + 97);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m + n)
空间复杂度O(n)

其中 m 是移位操作的数量，n 是字符串的长度。

相关题目