LeetCode Digest
3 分鐘 閱讀文 (大約 422 個字)

409. Longest Palindrome

題目
思路

  1. 怎麼判斷一個 string 是否為 palindrome？
    • (x) 做一個倒過來的 string 看看兩個是否相等
      • 需要 O(n) 時間複雜度，太長了，因為你必須對所有的字串組合做測試
    • (o) Palindrome 一定是由偶數個數的字母組成，頂多再加上一組奇數個數的字母
  2. 先用 dict 記錄每個 character 的個數，再利用計算完成的 dict 來算出答案

想完之後覺得應該蠻簡單，結果寫完送出…… Wrong Answer!

Wrong Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestPalindrome(self, s: str) -> int:
    # Build dict for characters.
    d = defaultdict(int)
    for c in s:
        d[c] += 1
        
    max_odd = 0
    count = 0
    for freq in d.values():
        if freq % 2 == 0:
            count += freq
        elif freq > max_odd:
            max_odd = freq
    return count + max_odd

錯誤之處在於我除了把偶數個數的字母納入之外，只挑了一個出現最多次的奇數字母納入答案，忘了其實奇數個數的字母可以拆成偶數… 所以會少算到很多

但這樣做完之後，要記得假如裡面有奇數次的字母，最後的答案要再加一

Python 3 solution：調整後的正確答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestPalindrome(self, s: str) -> int:
    # Build dict for character count.
    d = defaultdict(int)
    for c in s:
        d[c] += 1
        
    odd_complement = False
    count = 0
    for freq in d.values():
        if freq % 2 == 0:
            count += freq
        else:
            odd_complement = True
            count += freq - 1
    return count + odd_complement

最後提一下那個 count + odd_complement，Python 在遇到整數和布林值相加的時候，會把布林值轉為整數再相加 (True => 1, False => 0)，覺得是還不錯的 feature

  • 浮點數和布林值相加也類似，會把布林值作轉換後再相加 (True => 1.0, False => 0.0)
# , , ,
[Python] list 用 `.extend()` 與 `+=` 的差別
121. Best Time to Buy and Sell Stock

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×