a. First, I would fix the spelling of the function to is_palindrome
and give the variables within the function more semantic meaning. (i.e. s
could be string
).
Next, I would tackle time and space complexity. In the first for
loop we are recreating s
which already exists and incurring an O(n^2)
time complexity while doing it. This is because strings in Python are immutable. So our first loop is O(n)
and the act of recreating our r
string on each pass is also O(n)
giving us an O(n^2)
time complexity. Creating a new string in memory also gives us an O(n)
space complexity.
Lastly, there is no reason to set our x
value to True
on each iteration. If the reversed string and the string do not match, then it isn't a palindrome and we can immediately return False
.
I would improve this code by creating two pointers: a left index (0) and a right index (length of the string minus one). Then while the left index is less than the right index, I would check to see if the input string's value at it's left index does not equal the input string's value at it's right index. If this condition holds True
, this is not a palindrome and we can return False
. Otherwise, we'll increment our first index and decrement our last index. If our loop finishes, we'll return True
. This will give us an O(n)
time and O(1)
space complexity.
b. https://github.com/QMaximillian/phillies-qualifying-offer