In this problem, we will perform M reverse queries on the given string according to the array values.
The naïve approach to solving the problem is to reverse each string segment according to the given array value.
The optimized approach uses the logic that when we reverse the same substring two times, we get the original string.
Problem statement − We have given an alpha string containing the alphabetical characters. Also, we have given an arr[] array of size M containing the positive integers. We need to perform the M operations on the given string and return the final string.
In each operation, we need to take the arr[i] and reveres the substring arr[i] to N − arr[i] + 1.
示例例子
输入
alpha = "pqrst"; arr = {2, 1};
登录后复制
输出
tqrsp
登录后复制
Explanation
-
执行第一个查询后，字符串变为 'psrqt'。
-
执行第二个查询后，我们得到了 'tqrsp'。
输入
− alpha = "pqrst"; arr = {1, 1};
登录后复制
输出
− ‘pqrst’
登录后复制
Explanation − 如果我们对同一个查询执行偶数次，我们会得到相同的字符串。
输入
− alpha = "pqrst"; arr = {1, 1, 1};
登录后复制
输出
− ‘tsrqp’
登录后复制
Explanation − If we perform the same query for an odd number of times, we get the reverse of the string.
Approach 1
In this approach, we will use the reverse() method to reverse the substring. We will take the starting and ending pointers using the given query and reverse the substring of the given string.
Algorithm
步骤 1 - 开始遍历查询数组。
第2步 - 使用arr[p] - 1初始化'left'变量。
Step 3 − Initialize the ‘right’ variable with str_len − arr[p] + 1.
Step 4 − Use the reverse() method to reverse the substring from left pointer to right pointer.
Example
#include
using namespace std;
void reverseStrings(string &alpha, int str_len, vector &arr, int arr_len){
// Traverse all queries
for (int p = 0; p < arr_len; p++){
// Get starting pointer
int left = arr[p] - 1;
// Ending pointer
int right = str_len - arr[p] + 1;
// Reverse the string
reverse(alpha.begin() + left, alpha.begin() + right);
}
}
int main(){
int str_len = 5;
string alpha = "pqrst";
int arr_len = 2;
vector arr = {2, 1};
reverseStrings(alpha, str_len, arr, arr_len);
cout
