Hash+Reverse+O(1) Space cheating solution for C++


  • 0

    This method tries to extract direction-dependent features in both directions and check if they are equal.
    I design a hash function to combine the elements into a feature variable(code[i]) in particular order thus the feature variable can be a summarize of all elements with direction feature.
    It is of course a cheating solution coz there is no one-to-one mapping for vector to integer.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(head == NULL || head->next == NULL)return true;
            int len = 0;
    
            // two hash mask numbers
            int m1 = 0x13349057;
            int m2 = 0x34129522;
            
            // used to store hash codes
            int code[] = {0,0,0,0};
            
            // get the hash codes from v[0] to v[n-1]
            ListNode* ptr = head;
            while(true){
                code[0] = dohash(code[0], ptr->val, m1);
                code[1] = dohash(code[1], ptr->val, m2);
                len++;
                if(ptr->next == NULL)break;
                ptr = ptr->next;
            }
            
            //ptr->next = head;
            
            ptr = head;
            ListNode* pre = NULL;
            ListNode* pro = NULL;
    
    
            // reverse the whole linklist
            while(true){
                pro = ptr->next;
                ptr->next = pre;
                pre = ptr;
                if(pro == NULL)break;
                ptr = pro;
            }
    
    
    
            // get the hash codes from v[n-1] to v[0]
            while(true){
                code[2] = dohash(code[2], ptr->val, m1);
                code[3] = dohash(code[3], ptr->val, m2);
                len++;
                if(ptr->next == NULL)break;
                ptr = ptr->next;
            }
    
    
            // double check if the hash codes equal
            return code[0] == code[2] && code[1] == code[3];
            
        }
        
        int dohash(int a, int b, int mask){
            int tmp = b*b*b + 3;
            return (a + tmp) ^ mask;
        }
    };
    

Log in to reply
 

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