Skip to content

Instantly share code, notes, and snippets.

@QMaximillian
Last active March 20, 2021 01:05
Show Gist options
  • Save QMaximillian/2437d1dd676fec8171b8d97737a74aed to your computer and use it in GitHub Desktop.
Save QMaximillian/2437d1dd676fec8171b8d97737a74aed to your computer and use it in GitHub Desktop.

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment