| 41 | import itertools |
| 42 | |
| 43 | class Solution(object): |
| 44 | |
| 45 | # beat 33% |
| 46 | def longestPalindrome(self, s): |
| 47 | |
| 48 | if len(s) <= 1: |
| 49 | return s |
| 50 | |
| 51 | # {"c": [0], "b": [1, 2], "d": [3]} |
| 52 | s_dict = {} |
| 53 | for i, d in enumerate(s): |
| 54 | try: |
| 55 | s_dict[d].append(i) |
| 56 | except KeyError: |
| 57 | s_dict[d] = [i] |
| 58 | # print(s_dict) |
| 59 | |
| 60 | # {2: [(1, 3), (2, 4)]} |
| 61 | value_dict = {} |
| 62 | |
| 63 | for i in s_dict: |
| 64 | if len(s_dict[i]) >= 2: |
| 65 | for j in self.makeCombinations(s_dict[i]): |
| 66 | try: |
| 67 | value_dict[j[1]-j[0]].append(j) |
| 68 | except KeyError: |
| 69 | value_dict[j[1]-j[0]] = [j] |
| 70 | # print(value_dict) |
| 71 | for i in sorted(value_dict, reverse=True): |
| 72 | for j in value_dict[i]: |
| 73 | x = s[j[0]:j[1]+1] |
| 74 | if x == x[::-1]: |
| 75 | return x |
| 76 | |
| 77 | return s[0] |
| 78 | |
| 79 | |
| 80 | |
| 81 | def makeCombinations(self, split_list): |
| 82 | |
| 83 | return itertools.combinations(split_list, 2) |
| 84 | |
| 85 | # wrong |
| 86 | # def longestPalindrome(self, s): |
| 87 | # """ |
| 88 | # :type s: str |
| 89 | # :rtype: str |
| 90 | # """ |
| 91 | # # if len(s) == 1: |
| 92 | # # return s |
| 93 | |
| 94 | # findall = re.findall(r'((?P<letter>.{1}).*(?P=letter))', s) |
| 95 | # print(findall) |
| 96 | # for i in sorted(findall, reverse=True, key=lambda x: len(x[0])): |
| 97 | # if i[0] == i[0][::-1]: |
| 98 | # return i[0] |
| 99 | |
| 100 | # if not s: |
no outgoing calls
no test coverage detected