Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

bool isPalindrome(char* s) { int i, j, len; len = strlen(s); i = 0; j = len - 1; while(i < j){        // skip non alpha chars from start        while(i < len && !isalnum(s[i])){ i++; }         // skip non alpha chars from end        while(j >= 0 && !isalnum(s[j])){ j--; }         if(i < j && tolower(s[i]) != tolower(s[j])){ return false; }         i++; j--; } return true; }

Read More

9. Palindrome Number

Determine whether a given integer is a palindrome or not. Do this without extra space.

Note that the negative integers are assumed to be non-palindromic. Also, you are not allowed to convert the integer to string, given the restriction of using extra space.

Approach:

Return false if the given integer is negative. Otherwise, reverse the given integer and return true if the reversed integer and the given integer are both same else false.

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        
        int rem, revX = 0;
        int temp = x;
        while(temp > 0){
            rem = temp % 10;
            revX = revX * 10 + rem;
            temp = temp / 10;
        }
        return revX == x;
    }
};

Here is the link to ideone solution : http://ideone.com/9YyJke

Read More

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

This problem involves solution to the reverse linked list problem.

Follow up:

Could you do it in O(n) time and O(1) space?

Approach: Reverse the linked list after the middle and see if the first half is equal to the reversed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL){ return true; } ListNode *slow, *fast; slow = head; fast = head; while(fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } ListNode *secondHead = slow->next; slow->next = NULL; //reverse second part of the list ListNode *prev = NULL, *curr, *next = secondHead; while(next){ curr = next; next = next->next; curr->next = prev; prev = curr; } //compare two sublists now ListNode *p = curr; ListNode *q = head; while(p){ if(p->val != q->val) return false; p = p->next; q = q->next; } return true; } };

Read More