This notebook was prepared by Donne Martin. Source and license info is on GitHub.
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:
from __future__ import division
class ReverseString(object):
def reverse(self, chars):
if chars:
size = len(chars)
for i in range(size // 2):
chars[i], chars[size - 1 - i] = \
chars[size - 1 - i], chars[i]
return chars
This question has an artificial constraint that prevented the use of the slice operator and the reversed method. For completeness, the solutions for these are provided below. Note these solutions are not in-place.
class ReverseStringAlt(object):
def reverse_string_alt(string):
if string:
return string[::-1]
return string
def reverse_string_alt2(string):
if string:
return ''.join(reversed(string))
return string
%%writefile test_reverse_string.py
import unittest
class TestReverse(unittest.TestCase):
def test_reverse(self, func):
self.assertEqual(func(None), None)
self.assertEqual(func(['']), [''])
self.assertEqual(func(
['f', 'o', 'o', ' ', 'b', 'a', 'r']),
['r', 'a', 'b', ' ', 'o', 'o', 'f'])
print('Success: test_reverse')
def test_reverse_inplace(self, func):
target_list = ['f', 'o', 'o', ' ', 'b', 'a', 'r']
func(target_list)
self.assertEqual(target_list, ['r', 'a', 'b', ' ', 'o', 'o', 'f'])
print('Success: test_reverse_inplace')
def main():
test = TestReverse()
reverse_string = ReverseString()
test.test_reverse(reverse_string.reverse)
test.test_reverse_inplace(reverse_string.reverse)
if __name__ == '__main__':
main()
Overwriting test_reverse_string.py
%run -i test_reverse_string.py
Success: test_reverse Success: test_reverse_inplace
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:
# %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;
}