C++程序 检查是否可以通过旋转另一个字符串d个位置来获得字符串

C++程序 检查是否可以通过旋转另一个字符串d个位置来获得字符串

给定两个字符串 str1str2 ,以及一个整数 d ,任务是检查是否可以通过将 str1 旋转 d 个位置(向左或向右)来获取 str2

例子:

输入: str1 = “abcdefg”, str2 = “cdefgab”, d = 2

输出: Yes

将str1向左旋转2个位置。

输入: str1 = “abcdefg”, str2 = “cdfdawb”, d = 6

输出: No

方法: 解决相同问题的方法已在此处讨论。在本文中,反向算法用于在O(n)时间内向左和向右旋转字符串。如果 str1 的任何一个旋转等于 str2 ,则打印 Yes ,否则打印 No

下面是上述方法的实现:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to reverse an array from left
// index to right index (both inclusive)
void ReverseArray(string& arr, int left, int right)
{
    char temp;
    while (left < right) {
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}
 
// Function that returns true if str1 can be
// made equal to str2 by rotating either
// d places to the left or to the right
bool RotateAndCheck(string& str1, string& str2, int d)
{
 
    if (str1.length() != str2.length())
        return false;
 
    // Left Rotation string will contain
    // the string rotated Anti-Clockwise
    // Right Rotation string will contain
    // the string rotated Clockwise
    string left_rot_str1, right_rot_str1;
    bool left_flag = true, right_flag = true;
    int str1_size = str1.size();
 
    // Copying the str1 string to left rotation string
    // and right rotation string
    for (int i = 0; i < str1_size; i++) {
        left_rot_str1.push_back(str1[i]);
        right_rot_str1.push_back(str1[i]);
    }
 
    // Rotating the string d positions to the left
    ReverseArray(left_rot_str1, 0, d - 1);
    ReverseArray(left_rot_str1, d, str1_size - 1);
    ReverseArray(left_rot_str1, 0, str1_size - 1);
 
    // Rotating the string d positions to the right
    ReverseArray(right_rot_str1, 0, str1_size - d - 1);
    ReverseArray(right_rot_str1, str1_size - d, str1_size - 1);
    ReverseArray(right_rot_str1, 0, str1_size - 1);
 
    // Comparing the rotated strings
    for (int i = 0; i < str1_size; i++) {
 
        // If cannot be made equal with left rotation
        if (left_rot_str1[i] != str2[i]) {
            left_flag = false;
        }
 
        // If cannot be made equal with right rotation
        if (right_rot_str1[i] != str2[i]) {
            right_flag = false;
        }
    }
 
    // If both or any one of the rotations
    // of str1 were equal to str2
    if (left_flag || right_flag)
        returntrue;
    return false;
}
 
// Driver code
int main()
{
 
    string str1 = "abcdefg";
    string str2 = "cdefgab";
 
    // d is the rotating factor
    int d = 2;
 
    // In case length of str1 < d
    d = d % str1.size();
 
    if (RotateAndCheck(str1, str2, d))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}  

输出:

Yes

时间复杂度: O(n),其中n表示给定字符串的大小。

辅助空间: O(n),其中n表示给定字符串的大小。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例