CTCI-Q1.2

The question is:

1
Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.

We have two solutions here, the first is to swap the i and n-i-1 element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>

using namespace std;


void swap(char &a, char &b){
  a = a^b;
  b = a^b;
  a = a^b;
}

void reverse(char *s){
  int n = strlen(s);
  int i;
  for (i = 0; i < n/2; i++) {
    swap(s[i], s[n-i-1]);
  }
}

int main(){
  char s1[] = "123456789";
  char s2[] = "abcdefg";
  reverse(s1);
  cout<<s1<<endl;
  reverse(s2);
  cout<<s2<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>

using namespace std;

void reverse(char *str){
  char* end = str;
  char tmp;
  if(str){
    while(*end){
      ++end;
    }
    --end;
    //find the end of the string, since the last char is nul, we use --end to set one char back.
    while(str < end){
      tmp = *str;
      *str++ = *end;
      *end-- = tmp;
    }
  }
}

int main(){
  char s1[] = "123456789";
  char s2[] = "abcdefg";
  reverse(s1);
  cout<<s1<<endl;
  reverse(s2);
  cout<<s2<<endl;
}

For the python version, we use recursion to get the last char of the string first and then the second to last char by using the recursion method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/local/bin/python3
# -*- coding: utf-8 -*-


def reverseStringRecursive(str):
    if str != "":
        return str[-1:] + reverseStringRecursive(str[:-1])
    else:
        return ""



str1 = "abcdef"
str2 = "123456"

print(reverseStringRecursive(str1))
print(reverseStringRecursive(str2))

This method is very elegant.

As to the java version, I have no idea how to implement it in java: so sad!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution{
  public static void swap(char a, char b){
    char temp;
    temp = a;
    a = b;
    b = temp;
  }

  public static String reverse(String s){
    int n = s.length();
    int i;
    for (i=0; i<n/2; i++) {
      swap(s.charAt(i), s.charAt(n-i-1));
    }
    return s;
  }

  public static void main(String[] args){
    String str = "abcdef";
    Solution slt = new Solution();
    System.out.println("the original string is " + str + " and the reversed string is:\n" + slt.reverse(str));
  }
}