Leetcode_by_Python/005_palindromicSub.py at main · 4daJKong/Leetcode_by_Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        res = []
        for i in range (0, n):
            # if i == 3:
            #     print(res)

            temp_odd = []
            temp_even = []
            temp = []


            j = 0
            temp_odd.append(s[i])
            while (s[i - j] == s[i + j]):
                if j != 0:
                    temp_odd.append(s[i + j])
                    temp_odd.insert(0, s[i - j])
                j = j + 1
                if (i - j < 0 or i + j >= n):
                    break


            j = 0
            if i + 1 < n and s[i] == s[i + 1]:
                temp_even.append(s[i])
                temp_even.append(s[i + 1])
                while(s[i - j] == s[i + 1 + j]):
                    if j != 0:
                        temp_even.insert(0, s[i - j])
                        temp_even.append(s[i + 1 + j])
                    j = j + 1
                    if i - j < 0 or i + j + 1 >= n:
                        break

            if len(temp_odd) >= len(temp_even):
                temp = temp_odd
            else:
                temp = temp_even
            if len(temp) > len(res):
                res = temp

        return "".join(res)

    def longestPalindrome_demo(self, s: str) -> str:
        res = ''
        n = len(s)
        for i in range(0, n):
            for j in range(n, i, -1):
                if len(res) >= j - i:
                    break
                elif s[i: j] == s[i: j][::-1]:
                    res = s[i: j]

        return res


print(Solution().longestPalindrome_demo(s = "bananas")) #anana
print(Solution().longestPalindrome_demo(s = "cbaabf")) #baab
print(Solution().longestPalindrome_demo(s = "babad"))
print(Solution().longestPalindrome_demo(s = "bbbbb"))
print(Solution().longestPalindrome(s = "cbbd"))
print(Solution().longestPalindrome(s = "a"))
print(Solution().longestPalindrome(s = "ac"))
print(Solution().longestPalindrome(s = "abracadabra"))
print(Solution().longestPalindrome(s = "aba"))
print(Solution().longestPalindrome_demo(s = "abba"))
print(Solution().longestPalindrome_demo(s = "level"))


    # def longestPalindrome_demo(self, s: str) -> str:

    #     T = '#'.join('^{}$'.format(s))
    #     # T = s
    #     P = [0] * len(T)
    #     R, C = 0, 0
    #     for i in range(1,len(T) - 1):
    #         if i < R:
    #             P[i] = min(P[2 * C - i], R - i)

    #         while T[i+(P[i]+1)] == T[i-(P[i]+1)]:
    #             P[i] += 1

    #         if i + P[i] > R:
    #             R, C = i + P[i], i
    #     return P