0
def isPalindrome(s):
    if not s:
        return True
    st = "".join(char for char in s if char.alphanum()).lower()
    return st == st[::-1]

From what I understand, the reverse slicing [::-1] is O(n). However I'm not sure about join()'s time complexity, does it create a new string every time and iterate over it? Wouldn't that make it O(n^2)?

diagoot
  • 39
  • 1
  • 7
  • O(4n) => O(n) based on 1 for the join, 1 for the iteration over s, 1 for lower(), and 1 for reverse. Not all of these take the same amount of time in Python of course. – thebjorn Jan 17 '21 at 22:08
  • join will be O(N), where `N` is the result length of the resulting string. Basically, `join` exists to *allow* for the linear-time joining of many strings in Python, because otherwise, `str` objects are immutable and this isn't possible (well, perhaps there are very unwieldy ways to create such a string, e.g. using a `bytearray` or other buffer-like structure) – juanpa.arrivillaga Jan 17 '21 at 22:10
  • @juanpa.arrivillaga thanks, so join() allows strings to be mutable? – diagoot Jan 17 '21 at 22:16
  • 2
    @diagoot no, no it doesn't at all. It just implements the algorithm in the C layer, it is a built-in method of `str` objects so it uses `str` internals which are not accessible to the outside. – juanpa.arrivillaga Jan 17 '21 at 22:17

0 Answers0