C++程序通过执行给定的移位操作修改字符串

给定一个包含小写英文字母的字符串 S 和一个由形如 {direction, amount} 的对组成的矩阵 shift[][] ，其中方向可以是 0（表示左移） 或 1（表示右移） ， amount 是需要将 S 字符串向前移动的索引数。任务是返回可通过执行给定操作获得的修改后的字符串。

_注意：将第一个字符从 S 中移除并将其添加到末尾，称为左移1.类似地，将最后一个字符从 **S 中移除并插入到开头，称为右移1。

示例

输入： S = “abc”，shift[][] = {{0, 1}, {1, 2}}

输出： cab

解释：

[0，1]表示将S [0]向左移1。因此，从“abc”修改后字符串S变成“bca”。

[1，2]表示将S [0]向右移1。因此，从“bca”修改后字符串S变成了“cab”。

输入： S =“abcdefg”，shift[][] = {{1, 1}, {1, 1}, {0, 2}, {1, 3}}

输出： efgabcd

解释：

[1，1]表示将S [0]向右移1。因此，从“abcdefg”修改后字符串S变成“gabcdef。”

[1，1]表示将S [0]向右移1。因此，从“gabcdef”修改后字符串S变成“fgabcde”。

[0，2]表示将S [0]向左移2。因此，从“fgabcde”修改后字符串S变成“abcdefg”。

[1，3]表示将S [0]向右移3。因此，从“abcdefg”修改后字符串S变成“efgabcd。”

朴素方法： 解决此问题的最简单方法是遍历矩阵 shift[][] ，并将 S[0] 根据指定方向的索引数移动。在完成所有移位操作后，打印得到的最终字符串。

时间复杂度： O(N2)

辅助空间： O(N)

高效方法： 为了优化上述方法，请执行以下步骤：

初始化变量 val 以存储有效移位数。
遍历矩阵 shift[][] ，并对每个 第i行 执行以下操作：
如果 shift[i][0] = 0 （左移），则将 val 减去 - shift [i] [1] 。
否则（右移），将 val 增加 shift [i] [1] 。
更新 val = val％len （以进一步优化有效位移）。
初始化字符串 result = “” 以存储修改后的字符串。
现在，检查 if val >0。如果结果为真，则按 val 向右旋转字符串。
否则，按 |val| 向左旋转字符串。
打印 result 。

下面是上述方法的实现：

// 上述方法的C++实现
#include
using namespace std;

// 执行给定的偏移量操作后找到得到的字符串
void stringShift(string s，
                 vector>& shift)
{
    int val = 0;

    for (int i = 0; i < shift.size(); ++i)

        // 如果shift [i] [0] = 0，那么向左移动
        // 否则，向右移动
        val += shift[i][0] == 0
                   ? -shift[i][1]
                   : shift[i][1];

    // 存储字符串的长度
    int len = s.length();

    // 有效偏移量计算
    val = val % len;

    // 存储修改后的字符串
    string result = "";

    // 右旋转
    if (val > 0)
        result = s.substr(len - val, val)
                 + s.substr(0, len - val);

    // 左旋转
    else
        result 
            = s.substr(-val, len + val)
              + s.substr(0, -val);

    cout << result;
}

// 驱动程序
int main() {
    string s = "abc";
    vector> shift = {
        { 0, 1 },
        { 1, 2 }
    };

    stringShift(s, shift);

    return 0;
}

输出：