LeetCode 409 最長迴文串

2022-09-22 06:11:37 字數 2260 閱讀 8900

問題描述:

給定一個包含大寫字母和小寫字母的字串,找到通過這些字母構造成的最長的迴文串。

在構造過程中,請注意區分大小寫。比如"aa"不能當做一個迴文字串。

注意:

假設字串的長度不會超過 1010。

示例 1:

輸入:

"abccccdd"

輸出:7

解釋:我們可以構造的最長的迴文串是"dccaccd", 它的長度是 7。

思路:

even = all

odd = odd -1

1

from collections import

counter

2class

solution(object):

3def

longestpalindrome(self, s):

4"""

5:type s: str

6:rtype: int

7"""8#

"hdfahfodasfh"

9 dic =counter(s)

10 odd = 1

11 even =0

12 flag =true

13return

dic.items()

14for key,val in

dic.items():

15if val % 2 ==0:

16 even +=val

17elif val % 2 == 1 and val != 1:

18 odd += val -1

19 flag = false#

如果有大於等於3個相同的,則個數為1的不記入

20elif val == 1 and

flag:

21 odd += 1

22 flag =false

23return 9000

24return odd + even

方法2:

1

from collections import

counter

2class

solution(object):

3def

longestpalindrome(self, s):

4"""

5:type s: str

6:rtype: int

7"""8#

"hdfahfodasfh"

9 lis =

10 odd = 1 #假設[5,3,3,2,1]則odd = 5 + 3-1 + 3-1 為了統一成val-1 把初值設為1

11 even =0

12 flag =true

13 x =set(s)

14for i in

x:15

16lis.sort()

17 lis = lis[::-1]

18 flag2 =false #[4,2,1,1]的情況,如果沒有大於等於3的數,則要把odd初值1減去。

19for val in

lis:

20if val % 2 ==0:

21 even +=val

22elif val % 2 == 1 and val != 1:

23 odd += val -1

24 flag2 =true

25 flag = false#

如果有大於等於3個相同的,則個數為1的不記入

26elif val == 1 and

flag:

27 odd += 1

28 flag =false

29if

notflag2:

30 odd -= 1

31return odd + even

此方法待優化。

2018-09-30 17:53:50

leetcode 1278 分割回文串

time o n 2 k space o n 2 class solution j range from 0 i 1 k range fro...

LeetCode409 最長迴文串 數學題

一開始覺得這個題目很難,但是仔細看一下,其實是拿字串裡面的字元來構造迴文串。 怎樣才能構造迴文串呢? 對稱的才是迴文串,所以只要有偶數個同樣的字元就行了。 比如aaaabbcbbaaaa 1 只要有偶數個相同的字元,那麼他們就能對稱分兩邊,肯定可以啊 2 中間加一個單個的字元就行,因為中間加上一個...