移动字母 II

2381。移动字母 II

难度：中等

主题：数组、字符串、前缀和

给定一个由小写英文字母组成的字符串 s 和一个二维整数数组 shifts，其中 shifts[i] = [start_i, end_i, Direction_i]。对于每个 i，shift s 中的字符从索引开始_i 到索引结束_i（包含）向前 if 方向_i = 1，或者如果方向_i = 则向后移动字符0.

移动字符向前意味着将其替换为字母表中的下一个字母（环绕以使“z”变成“a”）。同样，向后移动字符意味着将其替换为字母表中的前一个字母（环绕以使“a”变成“z”）。

返回

应用所有此类转换到 s 后的最终字符串。

示例1：

• 输入： s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
• 输出：“ace”
• 解释： 首先，将索引 0 的字符向后移动到索引 1。现在 s =“扎克”。
  其次，将字符从索引 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 4 shifts[i].length == 3
0 i i 0 i s 由小写英文字母组成。

提示：

您是否可以跟踪哪些字符被移动以及在所有班次中移动了多少字符，而不是在每个班次中移动每个字符？
尝试标记每个班次的开始和结束，然后执行班次​​的前缀和。

解决方案：

我们需要避免每次移位都将字符一个一个地移动，因为这对于大输入来说太慢了。相反，我们可以通过利用称为

前缀总和. 的技术来使用更优化的方法。

步骤：

1. 标记移位边界：我们不是立即移位每个字符，而是在每个范围的开始和结束处标记移位效果。
2. 应用前缀和：标记所有移位后，我们可以使用前缀和技术计算每个字符的累积移位。这使我们能够有效地将累积移位应用于每个字符。
3. 执行移位：一旦我们知道每个字符的总移位，我们就可以将移位（向前或向后）应用于字符串。

让我们用 PHP 实现这个解决方案：2381。移动字母 II

<?php /**
 * @param String $s
 * @param Integer[][] $shifts
 * @return String
 */
function shiftingLetters($s, $shifts) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function
$s1 = "abc";
$shifts1 = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
echo shiftingLetters($s1, $shifts1) . "\n";  // Output: "ace"

$s2 = "dztz";
$shifts2 = [[0, 0, 0], [1, 1, 1]];
echo shiftingLetters($s2, $shifts2) . "\n";  // Output: "catz"
?>

解释：

1. 对于每个移位 [开始、结束、方向]，我们将在开始处递增移位数组并在结束时递减 1。这使我们能够跟踪移位范围的开始和结束。
2. 处理完所有移位后，我们对移位数组应用前缀和，以获得每个索引处的累积移位。
3. 最后，我们将累积移位应用于字符串中的每个字符。

代码说明：

1. 输入解析：我们将输入字符串 s 转换为字符数组，以便于操作。
2. 移位数组：我们将大小为 n 1 的移位数组初始化为零。该数组用于跟踪移位效果。对于每个班次 [开始、结束、方向]，我们调整 shift[start] 和 shift[end 1] 处的值以反映班次的开始和结束。
3. 前缀总和：我们通过迭代移位数组并维护移位的累积和来计算每个字符的总移位。
4. 字符移位：对于字符串中的每个字符，我们使用公式 (ord(currentChar) - ord('a')totalShift) % 26 计算最终的移位字符，这说明了字符串的循环性质字母表。
5. 返回结果：将字符数组转回字符串并返回，得到最终的字符串。

时间复杂度：

• 时间复杂度：O(n m)，其中n是字符串s的长度，m是移位次数。这是因为我们每次迭代字符串和班次列表一次。
• 空间复杂度：O(n)，其中n是字符串s的长度，因为移位数组需要空间。

即使输入约束有上限，该解决方案也能有效处理问题。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是移动字母 II的详细内容。更多信息请关注PHP中文网其他相关文章！