205. Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note:
You may assume both s and t have the same length.
解：两个hash, 映射, {'e':'a', 'g':'d'}
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False
h_s, h_t = {}, {}
for i in xrange(len(s)):
if s[i] in h_s:
if h_s[s[i]] != t[i]:
return False
else:
h_s[s[i]] = t[i]
for i in xrange(len(t)):
if t[i] in h_t:
if h_t[t[i]] != s[i]:
return False
else:
h_t[t[i]] = s[i]
return True
65. Valid Number
Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
解：状态图
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
state = [{},
{'blank':1, 'sign':2, 'digit':3, '.':4},
{'digit':3, '.':4},
{'digit':3, '.':5, 'e':6, 'blank':9},
{'digit':5},
{'digit':5, 'e':6, 'blank':9},
{'sign':7, 'digit':8},
{'digit':8},
{'digit':8, 'blank':9},
{'blank':9}
]
currState = 1
for c in s:
if c >= '0' and c<= '9':
c = 'digit'
if c ==' ':
c = 'blank'
if c == '+' or c == '-':
c = 'sign'
if c not in state[currState].keys():
return False
currState = state[currState][c]
print c, currState
if currState not in [3, 5, 8, 9]:
return False
return True
**
- Minimum Window Substring**
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
解：two hash, and two pointers
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if s is None or t is None or len(t) > len(s):
return ""
d, dt = {}, dict.fromkeys(t, 0)
for ch in t:
d[ch] = d.get(ch, 0) + 1
pi, pj, cont = 0, 0, 0
ans = ""
while pj < len(s):
if s[pj] in dt:
if dt[s[pj]] < d[s[pj]]:
cont += 1
dt[s[pj]] += 1
if cont == len(t):
while pi < pj:
if s[pi] in dt:
if dt[s[pi]] == d[s[pi]]:
break
dt[s[pi]] -= 1
pi += 1
if ans =="" or pj - pi < len(ans):
ans = s[pi:pj+1]
dt[s[pi]] -= 1
pi += 1
cont -= 1
pj += 1
return ans
Two Strings Are Anagrams
"sorted_s = ''.join(sorted(s))
sorted_t = ''.join(sorted(t))
return sorted_s==sorted_t"
compare strings
"letters = collections.defaultdict(int)
for a in A:
letters[a] += 1
for b in B:
letters[b] -= 1
if b not in letters or letters[b] < 0:
return False
return True"
strStr
"if source is None or target is None:
return -1
for i in xrange(len(source)-len(target)+1):
for j in xrange(len(target)):
if source(i+j) != target(j):
break
else:
return i
return -1"
Anagrams
"dict = {}
for words in strs:
sortedword = ''.join(sorted(words))
dict[sortedword] = [word] if sortedword not in dict else dict[sortedword] + [word]
res = []
for item in dict:
if len(dict[item]) >= 2:
res += dict[item]
return res"
longest Common Substring
"ans = 0
for i in xrange(len(A)):
for j in xrange(len(B)):
l = 0
while i+l < len(A) and j+l < len(B) and A[i+l] == B[j+l]:
l += 1
if l > ans:
ans = l
return ans"
Longest Common Prefix
"if not strs or len(strs)==0: return ''
prefix = strs[0]
for i in range(1, len(strs)):
j = 0
while j < min( len(strs[i], len(prefix) ):
if strs[i][j] != prefix[j]:
break
j += 1
prefix = prefix[:j]
return prefix"
Student Attendance Record I
return not (s.count('A') > 1 or 'LLL' in s)
Repeated Substring Pattern
" if s is None: return False
for i in range(len(s)/2):
sub = s[0:i+1]
multi = len(s)/(i+1)
if s == sub*multi: return True
return False"
Longest Palindromic Substring
" def longestPalindrome(self, s):
""""""
:type s: str
:rtype: str
""""""
res = """"
for i in xrange(len(s)):
for k in xrange(2):
tmp = self.helper(s, i, i+k)
if len(tmp) > len(res):
res = tmp
return res
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]"
Longest Substring Without Repeating Characters
" def lengthOfLongestSubstring(self, s):
# write your code here
if len(s) == 0:
return 0
ans = 0
left = 0
last = {}
for i in range(len(s)):
if s[i] in last and last[s[i]] >= left:
left = last[s[i]] + 1
last[s[i]] = i
ans = max(ans, i - left +1)
return ans"
Compare Version Numbers
" version1 = [int(v) for v in version1.split(""."")]
version2 = [int(v) for v in version2.split(""."")]
for i in xrange(max(len(version1), len(version2))):
v1 = version1[i] if i < len(version1) else 0
v2 = version2[i] if i < len(version2) else 0
if v1 > v2:
return 1
elif v1 < v2:
return -1
return 0"
Reverse Words in a String
" def reverseWords(self, s):
""""""
:type s: str
:rtype: str
""""""
s = s.split()
s = s[::-1]
s = "" "".join(s)
return s"
Ransom Note
"def canConstruct(self, ransomNote, magazine):
""""""
:type ransomNote: str
:type magazine: str
:rtype: bool
""""""
for i in set(ransomNote):
if ransomNote.count(i) > magazine.count(i):
return False
return True"
Integer to Roman
"M = ["""", ""M"", ""MM"", ""MMM""]
C = ["""", ""C"", ""CC"", ""CCC"", ""CD"", ""D"", ""DC"", ""DCC"", ""DCCC"", ""CM""]
X = ["""", ""X"", ""XX"", ""XXX"", ""XL"", ""L"", ""LX"", ""LXX"", ""LXXX"", ""XC""]
I = ["""", ""I"", ""II"", ""III"", ""IV"", ""V"", ""VI"", ""VII"", ""VIII"", ""IX""]
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[(num%10)]"
- Letter Combinations of a Phone Number
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
res = []
mp = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
for i in xrange(len(digits)):
tmp = []
if digits[i] in mp:
for n in xrange(len(mp[digits[i]])):
if len(res):
for k in xrange(len(res)):
tmp.append(res[k] + mp[digits[i]][n])
else:
tmp.append(mp[digits[i]][n])
res = tmp[:]
return res
- Roman to Integer
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
mp = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
curSum = 0
for i in xrange(len(s)):
if i < len(s)-1 and mp[s[i]] < mp[s[i+1]]:
curSum -= mp[s[i]]
elif s[i] in mp:
curSum += mp[s[i]]
return curSum
- One Edit Distance sol, since dis only one, [abc, adc], [abc, ac], [ac, abc], if above all true, then the last character, check abs(l1-l2)
class Solution(object):
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
# s = abc, t = ac; s = abc, t = adc;
for i in xrange(min(len(s),len(t))):
if s[i] != t[i]:
if len(s) == len(t):
return s[i+1:] == t[i+1:]
elif len(s) < len(t):
return s[i:] == t[i+1:]
else:
return s[i+1:] == t[i:]
return abs(len(s)-len(t)) == 1
- Add Binary
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
if a == "":
return b
if b == "":
return a
if a[-1] == '1' and b[-1] == '1':
print a[:-1], b[:-1]
return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'
else:
return self.addBinary(a[:-1], b[:-1]) + str(int(a[-1]) + int(b[-1]))
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
indexa = len(a) - 1
indexb = len(b) - 1
cur = ""
carry = 0
while indexa >= 0 or indexb >= 0:
x = int(a[indexa]) if indexa >= 0 else 0
y = int(b[indexb]) if indexb >= 0 else 0
if (x + y + carry) % 2 == 0:
cur = '0' + cur
else:
cur = '1' + cur
carry = (x + y + carry) / 2
indexa, indexb = indexa-1, indexb-1
if carry == 1:
cur = '1' + cur
return cur
Remove Substrings sol: string.find(sub, start, end)
class Solution:
# @param {string} s a string
# @param {set} dict a set of n substrings
# @return {int} the minimum length
def minLength(self, s, dict):
# Write your code here
if not s:
return 0
import Queue
queue = Queue.Queue()
queue.put(s)
hash = set([s])
res = len(s)
while not queue.empty():
ss = queue.get()
for sub in dict:
found = ss.find(sub)
while found != -1:
new_s = ss[:found] + ss[found+len(sub):]
if new_s not in hash:
if len(new_s) < res:
res = len(new_s)
queue.put(new_s)
hash.add(new_s)
found = ss.find(sub, found+1)
return res
string to Integer (atoi) sol:
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str = str.strip()
if str == "":
return 0
i = 0
sign = 1
ret = 0
length = len(str)
MaxInt = (1<<31) - 1
if str[i] == '+':
i += 1
elif str[i] == '-':
i += 1
sign = -1
for i in range(i, length):
if str[i] < '0' or str[i] > '9':
break
ret = ret * 10 + int(str[i])
if ret > sys.maxint:
break
ret *= sign
if ret > MaxInt:
return MaxInt
if ret < MaxInt * -1:
return MaxInt * -1 -1
return ret