O(1) Space , O(n) Time C++ Solution


  • 0

    The Idea is have a table of 26 prime number with large difference between each other and sum all the prime at position in string 1 and do a sliding window on string 2.

    This is not an optimized code but just a different approach, please feel free to comment and provide ideas for optimization.

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            
            //Some Random 26 Prime Number with Large difference 
            //Each Prime Representing a Charecter.
           int prime[] = { 2, 31, 101, 223, 419, 599, 877, 1069, 1327, 1637, 1987, 2357, 2789, 3167, 3557, 3673, 3947, 4327, 4993, 5387, 5557, 5779, 6637, 7297, 7753, 7919 };
    
    	 if (s2.length() < s1.length())
    		 return false;
    
    	int s1Sum = 0;
    	for (int i = 0; i<s1.length(); i++)
    		s1Sum += prime[s1[i] -'a'];
    
    	int s2Sum = 0;
    	for (int i = 0; i<s1.length(); i++)
    		s2Sum += prime[s2[i] - 'a'];
    
    	if (s2Sum == s1Sum)
    		return true;
    	for (int i = s1.length(); i<s2.length(); i++)
    	{
    		s2Sum -=  prime[s2[i - s1.length() ] - 'a'];		
    		s2Sum +=  prime[s2[i] -'a'];
    		
    		if (s1Sum == s2Sum)
    			return true;
    	}
    
    	return false;
        }
    };
    

Log in to reply
 

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