## Topcoder SRM使用Python解题需谨慎 作者是 在线疯狂 发布于 2014年2月15日 在 topcoder-srm, 碎碎念.

Marco has a string S composed of lowercase letters. You are to reconstruct S from the given String[]s S1 and S2 as follows:
Concatenate in order all elements of S1 to make a string A.
Concatenate in order all elements of S2 to make a string B.
Finally, concatenate A and B to get S.
Return the number of palindromic substrings in S.
``````
import math,string,itertools,fractions,heapq,collections,re,array,bisect,random

class EllysNumberGuessing:
def isValid(self, num):
return num >= 1 and num <= 10 ** 9
cnt = cnt_dict.get(key)
if cnt is None:
cnt = 0
cnt_dict[key] = cnt + 1
def getCnt(self, cnt_dict, key):
cnt = cnt_dict.get(key)
if cnt is None:
cnt = 0
return cnt
def cntList(self, cnt_dict):
cnt_list = []
for key in cnt_dict:
cnt_list.append((key,cnt_dict[key]))
cnt_list = sorted(cnt_list, key = lambda k: k[1], reverse=True)
return cnt_list
#print pairs
cnt_dict = dict()
suspect = None
for pair in pairs:
if self.isValid(pair[0] + pair[1]) or self.isValid(pair[0] - pair[1]):
if self.isValid(pair[0] + pair[1]) and self.isValid(pair[0] - pair[1]):
if suspect is not None and pair[0] + pair[1] != suspect and pair[0] - pair[1] != suspect:
return -2
cnt_list = self.cntList(cnt_dict)
if len(cnt_list) > 1 and cnt_list[0][1] > cnt_list[1][1]:
suspect = cnt_list[0][0]
elif len(cnt_list) > 2 and cnt_list[1][1] == cnt_list[2][1]:
return -2
else:
num = 0
if self.isValid(pair[0] + pair[1]):
num = pair[0] + pair[1]
else:
num = pair[0] - pair[1]
cnt_list = self.cntList(cnt_dict)
if suspect is None:
if cnt_list[0][0] != num:
return -2
else:
suspect = num
elif suspect != num:
return -2
else:
return -2
cnt_list = self.cntList(cnt_dict)
if len(cnt_dict) == 0:
return -2
if len(cnt_list) > 1 and cnt_list[0][1] == cnt_list[1][1]:
return -1
return cnt_list[0][0]