As another example, we can look at the set of all palindromes. One way to check whether a string is a palindrome is to reverse it, and check that it is equal to its own reverse. This process requires storing a reversed copy of the string in memory. Since the string can be arbitrarily large, we require an arbitrarily large amount of memory. Any algorithm that I can come up with for determining whether a string is a palindrome runs into this same issue. By our rule of thumb, the set of palindromes is a non-regular language; this is indeed a fact which can be formally proved.
I'm pretty sure you can check if a string is a palindrome with O(1) space complexity? Just create a left pointer to the start of the string and a right pointer to the end and walk them towards the middle checking the chars they point to is equal each time?
I'm pretty sure you can check if a string is a palindrome with O(1) space complexity? Just create a left pointer to the start of the string and a right pointer to the end and walk them towards the middle checking the chars they point to is equal each time?