C++ code avoid countting and suming up all chars in each iteration


  • 0
    A
    class Map {
    
    public:
    	void clear()
    	{
    		memset(m, 0,sizeof(int)*26);
    		total = 0;
    	}
    	void add(char c)
    	{
    		++m[c - 'a'];
    		++total;
    	}
    	void sub(char c)
    	{
    		if (m[c - 'a'] >0)
    		{
    			--m[c - 'a'];
    			--total;
    		}
    	}
    	int query(char c)
    	{
    		return m[c - 'a'];
    	}
    
    
    	int m[26];
    	int total;
    };
    class Solution {
    
    public:
    	set<char> s;
    	Map m;
    
    	bool checkInclusion(string s1, string s2) {
    		if (s2.length() < s1.length())
    		{
    			return false;
    		}
    
    		m.clear();
    
    		for (char c : s1)
    		{
    			s.insert(c);
    			m.add(c);
    		}
    
    		auto start = s2.begin();
    
    		Map temp;
    		temp.clear();
    		for (auto iter = s2.begin(); iter != s2.end(); ++iter)
    		{
    			char c = *iter;
    			if (s.find(c) == s.end())
    			{
    				temp.clear();
    				start = iter;
    				continue;
    			}
    			temp.add(c);
    			if (temp.query(c) > m.query(c))
    			{
    			    do
    			    {
    			        temp.sub(*start);
    			    }
    				while (*start++ != c);
    			}
    			else if (temp.total == s1.size())
    			{
    				return true;
    			}
    
    		}
    		return false;
    	}
    };
    

Log in to reply
 

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