Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

Naive Thinking: At first I was considering using a hashmap, but that's taking O(n) space, definitely not efficient enough. It's definitely solvable in O(1) space.

 class Solution:  
   # @param A a list of integers  
   # @return an integer  
   def removeDuplicates(self, A):  
     fast = 0  
     slow = 0  
     while fast < len(A):  
       A[slow] = A[fast]  
       slow += 1  
       # when duplicate happens, go through all duplicates with current number  
       if fast+1 < len(A) and A[fast+1]==A[fast]:  
         A[slow] = A[fast+1]  
         slow += 1  
         i = 2  
         while fast+i < len(A) and A[fast+i] == A[fast]:  
           i += 1  
         fast += i  
       else:  
         fast += 1  
     return slow  

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true 

Solution1: standard DP

 class Solution:  
   # @return a boolean  
   def isMatch(self, s, p):  
     opt = [[False]*(len(p)+1) for x in range(len(s)+1)]  
     # base case  
     opt[0][0] = True  
     for j in xrange(1,len(p),2):  
       if p[j] == '*':  
         opt[0][j+1] = True  
       else:  
         break  
     # iteration  
     for i in xrange(1,len(s)+1):  
       for j in xrange(1,len(p)+1):  
         if s[i-1] == p[j-1] or p[j-1] == '.':  
           opt[i][j] = opt[i-1][j-1]  
         elif p[j-1] == '*':  
           opt[i][j] = opt[i][j-2] or ((s[i-1] == p[j-2] or p[j-2] == '.') and opt[i-1][j])  
     return opt[len(s)][len(p)]