A neat recursive c++ solution with detailed explanation


  • -2
    X

    This smart implementation shows up in several places but not in this discussion forum. So I post it here in case anyone finds it useful. Detailed explanation and references can be found in my blog.

    class Solution {
    public:
        bool isPalindrome(int x) {
            return isPalindromeHelper(x, x);
        }
        
        bool isPalindromeHelper(int x, int &y) {
    		if (x < 0) 	return false;
    		if (x == 0)	return true;
    		
    		/**
    		 * as call stack goes up,
    		 * x % 10 outputs digits from highest to lowest
    		 * y % 10 outputs digits from lowest to highest
    		 */
    		if (isPalindromeHelper(x / 10, y) && (x % 10 == y % 10)) {
    			y /= 10;
    			return true;
    		} else {
    			return false;
    		}
    	}
    };
    

  • 2
    J

    Recursion is not space constant。


  • 2
    S

    It's neither "neat" nor "smart".

    This code misuses recursion simply to make the illusion of constant space complexity. In essense, what you did was using the call stack instead of an array, but they both take O(n) space where n is ceil(log10(x)).


  • 0
    S

    My friend, I will give your vote up. Because we know that this problem is not about neat code or efficiency. It is about how coders could handle complex situations.

    if we need neat code, we shall just use a stack, simple.

    But for this problem, recursive solution could show we think and how to code.

    P.S.: For reality, recursion is never an option for this problem.


  • 0
    X

    Yes, that's my intention of posting this. I do not claim time or space efficiency.


  • 0
    P

    Bravo way to solve it use the recursion. In fact, the question is not clear about "extra space". Anyway ,interesting!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.