一下子发5题,Regular Expression Matching,Container With Most Water,Integer to Roman,Roman to Integer,Longest Common Prefix

Regular Expression Matching

最开始的解法没有会TLE, 那个case太贱了,然后hack一下就虽然那个case过了,但是后面的一个case还是会TLE,于是把递归稍微剪了一下

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
class Solution:
    # @return a boolean
    def isMatch(self, s, p):
    	p = str(p)
        alphas = set(list(p)) - {'*'}
        for k in alphas:
            pt = k + '*' + k + '*'
            while p.find(pt) != -1:
                p = p.replace(pt, k + '*')
    	def isMatch(s,p):
    		#print "debug",s,p
    		if p == '':
    			if s == '' : return True
    			else : return False
    		c = p[0]
        	if s == '':
        		if len(p) == 2 and p[1] == '*' : return True
        		if len(p) != 0 : return False
        		else : return True
        	if s == p : return True
        	else:
        		if len(p) >1 and p[1] == '*':
        			if c == s[0] or c == '.' : return isMatch(s[1:],p) or isMatch(s[1:],p[2:]) or isMatch(s,p[2:]) 
        			else : return isMatch(s,p[2:]) 
        		else:
        			if c == s[0] or c == '.' : return isMatch(s[1:],p[1:]) 
        			return False
        return isMatch(s,p)

 

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
class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        p = str(p)
        alphas = set(list(p)) - {'*'}
        for k in alphas:
            pt = k + '*' + k + '*'
            while p.find(pt) != -1:
                p = p.replace(pt, k + '*')
        def test(s,p):
            if p == '':
                return s == ''
            if s == '':
                return False
            else:
                return p[0] == s[0] or p[0] == '.'
        def isMatch(s,p):
            if p == '' :
                return s==''
            if len(p) >1 and p[1] == '*':
                if isMatch(s,p[2:]):
                    return True
                while test(s,p):
                    s = s[1:]
                    if isMatch(s,p[2:]):return True
            else:
                if not test(s,p): return False
                return isMatch(s[1:],p[1:])
            return False
        return isMatch(s,p)

Container With Most Water

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # @return an integer
    def maxArea(self, height):
        length = len(height)
        low,high = 0,length-1
        ret = 0
        while low < high:
            ret = max(ret,(high-low)*min(height[low],height[high]))
            if height[low]<height[high]:
                low += 1
            else:
                high -=1
        return ret

Integer to Roman

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # @return a string
    def intToRoman(self, num):
    	i2r = {1000:"M", 900:"CM", 500:"D", 400:"CD", 100:"C",90:"XC", 50:"L", 40:"XL", 10:"X", 9:"IX", 5:"V", 4:"IV", 1:"I"}
    	sorted_i=sorted(i2r.iterkeys(),reverse=True)
    	def intToRoman(num):
    		for i in sorted_i:
    			if i <= num:
    				return i2r[i] + intToRoman(num - i)
    		return ""
    	return intToRoman(num)

Roman to Integer

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
class Solution:
    # @return an integer
    def romanToInt(self, s):
    	ret = 0
        s = s[::-1]
        for c in s:
        	if c == 'I':
        		if ret > 5:
        			ret -= 1
        		else:
        			ret +=1
        	elif c == 'V':
        		ret += 5
        	elif c == 'X':
        		if ret > 50:
        			ret -= 10
        		else:
        			ret +=10
        	elif c == 'L':
        		ret += 50
        	elif c == 'C':
        		if ret > 500:
        			ret -= 100
        		else:
        			ret +=100
        	elif c == 'D':
        		ret += 500
        	elif c == 'M':
        		ret +=1000
        return ret

Longest Common Prefix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
    	length = len(strs)
    	if length == 0:
    		return ""
    	if length == 1:
    		return strs[0]
    	if length == 2:
    		length2 = min(len(strs[0]),len(strs[1]))
    		i = 0
    		ret = ''
    		while i<length2:
    			if strs[0][i] == strs[1][i]:
    				ret += strs[0][i]
    				i += 1
    			else:
    				break
    		return ret
    	if length > 2:
    		index = length / 2
    		return self.longestCommonPrefix([self.longestCommonPrefix(strs[:index]),self.longestCommonPrefix(strs[index:])])

 

Share This: 

Leave a Reply

Your email address will not be published. Required fields are marked *