This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).
Since Python strings are immutable, we'll use a list of chars instead to exercise in-place string manipulation as you would get with a C string.
Complexity:
Note:
In [1]:
from __future__ import division
def list_of_chars(chars):
if chars is None:
return None
size = len(chars)
for i in range(size//2):
chars[i], chars[size-1-i] = \
chars[size-1-i], chars[i]
return chars
In [2]:
def reverse_string_alt(string):
if string is None:
return None
return string[::-1]
def reverse_string_alt2(string):
if string is None:
return None
return ''.join(reversed(string))
In [3]:
%%writefile test_reverse_string.py
from nose.tools import assert_equal
class TestReverse(object):
def test_reverse(self):
assert_equal(list_of_chars(None), None)
assert_equal(list_of_chars(['']), [''])
assert_equal(list_of_chars(
['f', 'o', 'o', ' ', 'b', 'a', 'r']),
['r', 'a', 'b', ' ', 'o', 'o', 'f'])
print('Success: test_reverse')
def main():
test = TestReverse()
test.test_reverse()
if __name__ == '__main__':
main()
In [4]:
%run -i test_reverse_string.py
This is a classic problem in C/C++
We'll want to keep two pointers:
To get a pointer to the last char, we need to loop through all characters, take note of null terminator.
Complexity:
Note:
In [ ]:
# %load reverse_string.cpp
#include <stdio.h>
void Reverse(char* str) {
if (str) {
char* i = str; // first letter
char* j = str; // last letter
// find the end of the string
while (*j) {
j++;
}
// don't point to the null terminator
j--;
char tmp;
// swap chars to reverse the string
while (i < j) {
tmp = *i;
*i++ = *j;
*j-- = tmp;
}
}
}
int main() {
char test0[] = "";
char test1[] = "foo";
Reverse(NULL);
Reverse(test0);
Reverse(test1);
printf("%s \n", test0);
printf("%s \n", test1);
return 0;
}