Valid Palindrome
class Solution(object):
def isPalindrome(self, s):
s=s.lower()
result = []
for i in xrange(len(s)):
if s[i].isalnum():
result.append(s[i])
return result == result[::-1]
Implement strStr()
# KMP
class Solution(object):
def strStr(self, s, p):
i,j,m,n,nextArr = -1,0,len(s),len(p),[-1]*len(p)
while j<n-1:
if i==-1 or p[i]==p[j]:
i,j=i+1,j+1
nextArr[j]=i
else: i = nextArr[i]
i,j=0,0
while i<m and j<n:
if j==-1 or s[i]==p[j]:
i,j=i+1,j+1
else: j = nextArr[j]
if j==n: return i-j
return -1
String to Integer (atoi)
class Solution(object):
def myAtoi(self, s):
if len(s)==0:return 0
ls = list(s.strip())
sign = -1 if ls[0] == '-' else 1
if ls[0] in ['+','-']:del ls[0]
ret,i = 0,0
while i<len(ls) and ls[i].isdigit():
ret = ret*10 + ord(ls[i])-ord('0')
i+=1
return max(-2**31,min(sign*ret,2**31-1))
Add Binary
class Solution(object):
def addBinary(self, a, b):
if len(a)==0:return b
if len(b)==0:return a
if a[-1]=='1' and b[-1]=='1':
return self.addBinary(self.addBinary(a[0:-1],b[0:-1]),'1')+'0'
if a[-1]=='0' and b[-1]=='0':
return self.addBinary(a[0:-1],b[0:-1])+'0'
else:
return self.addBinary(a[0:-1],b[0:-1])+'1'
Longest Palindromic Substring
class Solution(object):
def longestPalindrome(self, s):
longest = 0
max_len=0
for i in xrange(len(s)):
if self.isP(s[i - max_len:i+1]):
longest = i - max_len
max_len = max_len + 1
elif i - max_len - 1 >= 0 and self.isP(s[i-max_len-1:i+1]):
longest = i - max_len - 1
max_len = max_len + 2
return s[longest:longest+max_len]
def isP(self,s):
return s == s[::-1]
Regular Expression Matching
class Solution(object):
def isMatch(self, s, p):
if not s and not p :return True
if s and not p:return False
if p[-1] == '*':
rep = p[-2]
if s and (s[-1]==rep or rep=='.'):
return self.isMatch(s[:-1],p) or self.isMatch(s,p[:-2])
else:
return self.isMatch(s,p[:-2])
else:
if s and (p[-1]==s[-1] or p[-1]=='.'):
return self.isMatch(s[:-1],p[:-1])
else:
return False
Wildcard Matching
class Solution(object):
def isMatch(self, s, p):
i,j,star=0,0,False
while i<len(s):
if j<len(p) and (p[j]=='?' or s[i]==p[j]):
i,j=i+1,j+1
continue
if j<len(p) and p[j]=='*':
star=True
tmpi,tmpj,j=i,j,j+1
continue
if star:
tmpi+=1
i,j=tmpi,tmpj+1
continue
return False
while j<len(p) and p[j]=="*": j+=1
if j==len(p): return True
return False
Longest Common Prefix
class Solution(object):
def longestCommonPrefix(self, strs):
if not strs:return ""
if len(strs) == 1 :return strs[0]
s,res=strs[0],''
for i in xrange(len(s)):
for j in xrange(1,len(strs)):
if i>=len(strs[j]) or strs[0][i]!=strs[j][i]:
return res
res+=strs[0][i]
return res
Valid Number
class Solution(object):
def isNumber(self, s):
hasPoint,hasE,hasNumber,numberAfterE=False,False,False,True
s=s.strip()
for i in xrange(len(s)):
if s[i] in '0123456789':
hasNumber=True
numberAfterE=True
elif s[i] == '.':
if hasPoint or hasE:
return False
hasPoint = True
elif s[i]=='e':
if hasE or not hasNumber:
return False
numberAfterE=False
hasE=True
elif s[i]=='-' or s[i]=='+':
if i!=0 and s[i-1]!='e':
return False
else:return False
return hasNumber and numberAfterE
Group Anagrams
class Solution(object):
def groupAnagrams(self, strs):
result,output = {},[]
for s in strs:
key = ''.join(sorted(s))
if key in result:
result[key].append(s)
else:
result[key] = [s]
print result
for r in result.values():
output.append(sorted(r))
return output
Simplify Path
class Solution(object):
def simplifyPath(self, path):
result = []
pathList = path.split('/')
for i in pathList:
if i:
if i == '..':
if len(result)>0:result.pop()
elif i!='.':
result.append(i)
return '/'+'/'.join(result)
Length of Last Word
class Solution(object):
def lengthOfLastWord(self, s):
if not s or len(s.strip()) < 1:
return 0
s = s.strip().split()
return len(s[-1])
