Обращение рекурсивной подстроки в 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() здесь, потому что он будет выбрасывать, если начало или конец находятся за пределами длины строки (например, вы передали -1 или 26).

Я предполагаю, что рекурсия была определена как часть назначения, но здесь это кажется плохим выбором. Если ваша подстрока имеет длину, скажем, миллион символов, программе потребуется отслеживать миллион вызовов функций, что, скорее всего, приведет к переполнению стека . На мой взгляд, скромное значение для l oop кажется более подходящим для этой задачи.

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;
}