class Solution(object):
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = [0, 0, 0]
cnt = [0] * len(nums)
for i in nums:
cnt[i-1] += 1
for i, c in enumerate(cnt):
ans[c] = i+1
return [ans[2], ans[0]]


class Solution(object):
def findLongestChain(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
pairs.sort()
ans, cur = 0, -2**32
for a, b in pairs:
if a > cur:
ans += 1
cur = b
else:
cur = min(b, cur)
return ans


class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
for i in xrange(len(s)):
j = k = i
while j >= 0 and k < len(s) and s[j] == s[k]:
ans += 1
j -= 1
k += 1
for i in xrange(len(s)-1):
if s[i] != s[i+1]:
continue
j, k = i, i+1
while j>=0 and k < len(s) and s[j] == s[k]:
ans += 1
j -= 1
k += 1
return ans


class Solution(object):
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
words = sentence.split(' ')
dict = set(dict)
ans = []
for word in words:
for i in xrange(len(word)):
if word[:i] in dict:
ans.append(word[:i])
break
else:
ans.append(word)
return ' '.join(ans)