[Leetcode] 1177. Can Make Palindrome from Substring (Medium)

概述

題目

https://leetcode.com/problems/can-make-palindrome-from-substring/
給一字串 s 與 queries，回傳一個由 True / False 組成之 array，其中 True 表示該 queries 時的啟、末與更動字母數，可讓該字串段變成回文，否則反之 False

心得

不會寫，看了解題才慢慢懂…QQ。從 BF 入手：每次 queries 抓前後 substring 再判斷是否改 k 次內可回文即能完成題目要求，但時間複雜度過高；進而判斷 substring、k 與可回文之關係，而又因題目是可以重新排列，故只需要判斷其奇偶穪即可，再透過 prefix 概念解之，queries 時兩兩對減就能滿足時間複雜度的要求

Prefix

思路

事先計算到第 i 位的 substring 奇偶性關係，而後前後對減判斷需修改的字母數是否 < k

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def canMakePaliQueries(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        n = len(s)
        dp = [Counter()]
        for i in range(n):
            dp.append(dp[i] + Counter(s[i]))
        
        ret = []
        for l, r, k in queries:
            dic = dp[r+1] - dp[l]
            # 因為可重排，故先 % 2 確保真正可能要替換的字母數量
            cnt = sum(v%2 for key, v in dic.items()) // 2
            ret.append(cnt <= k)
        return ret

Complexity

Time Complexity: O(n)
多幾次走過多少 queries 數值

Space Complexity: O(n)
用一 array 存其 prefix

Bucket

思路

from ye15，將沒有特定範圍的 Hash 改成有特定範圍 (26 英文單字) 的 Bucket

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def canMakePaliQueries(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        arr = [[0 for i in range(26)]]
        for c in s:
            pre = arr[-1].copy()
            pre[ord(c)-97] += 1
            arr.append(pre)
        
        ret = []
        for l, r, k in queries:
            cnt = sum((arr[r+1][i]-arr[l][i])%2 for i in range(26))
            ret.append(cnt <= 2*k+1)
        return ret

Complexity

Time Complexity: O(n)
多幾次走過多少 queries 數值

Space Complexity: O(n)
用一 array 存其 prefix

Bitwise

思路

from ye15，透過 Bitwise 運算來判斷 l, r 差異

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def canMakePaliQueries(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        arr = [0]
        for c in s:
            arr.append(arr[-1]^(1 << (ord(c)-97)))
        
        ret = []
        for l, r, k in queries:
            cnt = bin(arr[r+1] ^ arr[l]).count("1")
            ret.append(cnt <= 2*k+1)
        return ret

Complexity

Time Complexity: O(n)
多幾次走過多少 queries 數值

Space Complexity: O(n)
用一 array 存其 prefix