c++ - C++ 中的递归子串反转

Question

我不明白为什么下面的代码对此不起作用。该程序的任务是基于两个索引递归地反转字符串的一部分。对于递归的基本情况，我尝试了许多使用 swap() 和不同开始和结束条件的替代方法。我现在感觉真的很愚蠢，我在等待有人向我指出显而易见的事情。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string recurseReverse(string str, int start, int end);

int main() {
cout << "Starting string: ";
string alphabet = "abcdefghijklmnopqrstuvwxyz";
cout << alphabet;

cout << "Passing reverse the string along with values 11 and 18 for indices." << endl;
alphabet = recurseReverse(alphabet, 11, 18);
cout << alphabet << endl;

cout << "Passing reverse the string along with values 5 and 23 for indices." << endl;
alphabet = recurseReverse(alphabet, 5, 23);
cout << alphabet << endl;

cout << "Realphebetizing the string." << endl;
sort(alphabet.begin(), alphabet.end());
cout << alphabet << endl;

cout << "Dealphebetizing the string." << endl;
alphabet = recurseReverse(alphabet, 0, 25);
cout << alphabet << endl;

return 0;
}

string recurseReverse(string str, int start, int end) {
char temp = ' ';

if(start < end) {
temp = str[end - 1];
str[end - 1] = str[end];
str[end] = temp;
str = recurseReverse(str, start, end - 1);
}

return str;
}

Answer 1

我假设您想完全反转字符串，例如:
recurseReverse("abcde", 0, 4) => "edcba"
问题是您正在交换连续的元素。所以在第一次调用时，你交换了 d 和 e，然后 d 永远留在字符串的末尾。

相反，您应该交换字符串的第一个和最后一个元素，然后从两侧移入。

string recurseReverse(string str, int start, int end) {

  if(start < end) {
    std::swap(str.at(start), str.at(end));
    str = recurseReverse(str, start + 1, end - 1);
  }

  return str;
}

您应该使用 .at()在这里，因为如果 start 或 end 超出字符串的长度，它将抛出(例如，您传入了 -1 或 26)。

我假设递归被指定为分配的一部分，但在这里似乎是一个糟糕的选择。如果您的子字符串长度为一百万个字符，则程序需要跟踪一百万个函数调用 - 这很可能会导致 stack overflow .在我看来，简陋的 for 循环似乎更适合这项任务。

std::string reverseSubstring(std::string str, size_t start, size_t end) {

for(size_t left = start, right = end; left < right; ++left, --right)
{
    std::swap(str.at(left), str.at(right));
}

return str;
}

如果我正在编写生产代码，而不是作业，我只会让 STL 为我做这件事:

std::string reverseSubstring(std::string str, size_t start, size_t end) {

  if(start >= end || start < 0 || end >= str.size())
  {
    throw std::invalid_argument("start and end must be valid, and start must be before end");
  }
  std::reverse(str.begin() + start, str.begin() + end + 1);

  return str;
}