sundeepblue
4/15/2014 - 8:43 PM

reverse string. Given a string s of length n and an index i (0 <= i <= n). Using only constant extra space, how do you manipulate the string

reverse string. Given a string s of length n and an index i (0 <= i <= n). Using only constant extra space, how do you manipulate the string in-place to yield the string s[i, i+1, ... , n-1, 0, 1, ..., i-1]?

reverse_string.cpp
content_copyfile_download
void reverse1(string &s, int i, int j) {
     if(i < 0 || j >= s.size() || i > j || s.empty()) return;
     while(i <= j) {
          swap(s[i++], s[j--]);
     }
}

void manipulate(string &s, int i) {
     if(s.empty()) return;
     reverse1(s, 0, s.size()-1);
     int mid = s.size() - i - 2;
     reverse1(s, 0, mid);
     reverse1(s, mid+1, s.size()-1);
}