※ 引述《oin1104 (是oin的說)》之銘言：
: 題目
: 這字串能不能弄成K個回文字串
: 思路
: 一定要偶數才能弄到回文的兩邊
: 奇數只能放中間 所以不能超過k個
: class Solution {
: public:
: bool canConstruct(string s, int k)
: {
: int n = s.size();
: if(k == n )return 1;
: if(k > n)return 0;
: vector<int> save(26,0);
: for(char k : s)save[k-'a'] ++;
: int cnt = 0;
: for(int i = 0 ; i < 26 ; i ++)
: {
: if(save[i]%2 == 1)cnt ++;
: }
: return cnt <= k;
: }
: };
思路:
先統計各個字母個數
有兩種狀況無法達成題目要求:
1. 字母個數為奇數的數量 > k
2. s長度 < k
其他都能達成題目要求
python:
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
if len(s) < k:
return False
result = 0
record = [0] * 26
for c in s:
record[ord(c) - ord("a")] += 1
odd = 0
even = 0
for n in record:
if n % 2 == 1:
odd += 1
else:
even += 1
if odd > k:
return False
return True
應該是ㄅ 我沒想到會一次過==