【数组, 字符串, 后缀和】字母移位

题目

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 <= 10^5
• s 由小写英文字母组成
• shifts.length == s.length
• 0 <= shifts[i] <= 10^9

解题

方法一：倒序遍历 后缀和

思路

对于每个 shift[i] = x 会将 s 中的前 i + 1 个字母移位 x 次，也就是说每个 s[i] 会移位 $\sum\limits _{j=i}^{n - 1} shift[j]$ 次，如表格所示：

i	移位
0	shift[0] + shift[1] + shift[2] + … + shift[n - 1]
1	shift[1] + shift[2] + … + shift[n - 1]
2	shift[3] + … + shift[n - 1]
…	…
n-3	shift[n-3] + shift[n-2] + shift[n-1]
n-2	shift[n-2] + shift[n-1]
n-1	shift[n-1]

那么我们只需要先倒序遍历数组求后缀和然后再枚举字符串中每一个字符把它移位后缀和数组中对应的次数即可。

注意：由于 shifts[i] 最大可能是 10⁹ 所以求后缀和时可能会发生整形溢出，需要在每次对 26 取余后再累加。
代码中直接在原数组上进行了累加，没有新建后缀和数组。

代码

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        for (auto it = shifts.rbegin() + 1; it != shifts.rend(); ++it) {
            *it += *(it - 1) % 26;
        }
        for (int i = 0; i < s.length(); ++i) {
            s[i] = (s[i] - 'a' + shifts[i]) % 26 + 'a';
        }
        return s;
    }
};

方法二：一次遍历

思路

通过上面的代码易发现：每位后缀和只会使用一次，所以完全没必要构造出整个后缀和数组，在倒序遍历的过程中维护一个累加(accum)每次累加完成后移位字符即可。

代码

class Solution {
    static final char[] toChar = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

    public String shiftingLetters(String s, int[] shifts) {
        int accum = 0;
        char[] chs = s.toCharArray();
        for (int i = shifts.length - 1; i >= 0; --i) {
            accum = (accum + shifts[i]) % 26;
            chs[i] = toChar[(chs[i] - 'a' + accum) % 26];
        }
        return String.valueOf(chs);
    }
}

// 关闭同步流，与算法逻辑无关
int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
    const static int N = 0x3f3f3f3f;
    const char* to_char = new char[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

public:
    string shiftingLetters(string s, vector<int>& shifts) {
        int accum = 0;
        for (int i = shifts.size() - 1; i >= 0; --i) {
            accum += shifts[i];
            if (accum > N) accum %= 26;
            s[i] = to_char[(s[i] - 'a' + accum) % 26];
        }
        return s;
    }
};