Karl's Nest
0%

leetcode-day-14

Posted on In
Day-14 Perform String Shifts

LeetCode 30 days Challenge - Day 14

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

  • direction can be 0 (for left shift) or 1 (for right shift).
  • amount is the amount by which string s is to be shifted.
  • A left shift by 1 means remove the first character of s and append it to the end.
  • Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

1
2
3
4
5
Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

1
2
3
4
5
6
7
Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:  
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:

  • 1 <= s.length <= 100
  • s only contains lower case English letters.
  • 1 <= shift.length <= 100
  • shift[i].length == 2
  • 0 <= shift[i][0] <= 1
  • 0 <= shift[i][1] <= 100

Solution

题目要求分析：给定一个原始字符串以及一个位移指令集合shift，shift数组中，每个元素是一个二元组，依次表示对字符串进行的位移操作方向以及位数，要求返回最后处理完成的字符串。

解法：

本题提示中，说明了在限制条件下，直接暴力模拟也能通过，但这肯定不是我们想要的答案，为了尽可能减少“移动”操作，先来分析移动操作的特点：

  1. 方向0：向左移动amount个元素，实际上是将前amount个元素移动到字符串尾部。
  2. 方向1：向右移动amount个元素，实际上是将后amount个元素移动到字符串头部。

两次方向不同、amount相同的移动，将相互抵消：abcd -0,2-> cdab -1,2-> abcd。

由此，推断出最便利的做法是，先遍历shift数组，记录最终需要移动的步数（final_amount），具体措施：

  1. 遇到方向0，final_amount减去对应amount；
  2. 遇到方向1，final_amount加上对应amount；

最后，根据final_amount的正负（注意对长度取模，长度为n的字符串移动n次将恢复原状），依据移动操作的特点进行处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string stringShift(string s, vector<vector<int>>& shift) {
    string res = "";
    int final_amount = 0;
    for (auto v : shift) final_amount += v[0] ? v[1] : -v[1];
    if (final_amount > 0) {
        final_amount %= s.length();
        res = s.substr(0, s.length() - final_amount);
        res = s.substr(s.length() - final_amount) + res;
    }
    else {
        final_amount = (-final_amount) % s.length();
        res = s.substr(final_amount);
        res += s.substr(0, final_amount);
    }
    return res;
}

传送门：Perform String Shifts

Karl