สมมติว่าเรามีสตริง s และตัวเลข k เราต้องสร้าง k สตริง palindrome ที่ไม่ว่างเปล่าโดยใช้อักขระทั้งหมดใน s ดังนั้นที่นี่เราต้องตรวจสอบว่าเราสามารถใช้อักขระทั้งหมดใน s เพื่อสร้างสตริง k palindrome ได้หรือไม่
ดังนั้น หากอินพุตเป็นเหมือน "จริง" k =4 เอาต์พุตจะเป็น True เนื่องจากวิธีแก้ปัญหาเดียวที่เป็นไปได้คือการใส่อักขระแต่ละตัวในสตริงแยกกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ s
-
ถ้า n
-
คืนค่าเท็จ
-
-
ถ้า n เท่ากับ k แล้ว −
-
คืนความจริง
-
-
กำหนดหนึ่งแผนที่
-
สำหรับแต่ละอักขระ c ใน s
-
(เพิ่ม m[c] ขึ้น 1)
-
-
คี่ :=0
-
สำหรับคีย์-ค่าแต่ละคู่จะมีหน่วยเป็น m -
-
คี่ :=คี่ + (ค่าของมัน AND 1)
-
-
คืนค่าจริงเมื่อคี่ <=k มิฉะนั้นเป็นเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canConstruct(string s, int k) {
int n = s.size();
if (n < k)
return false;
if (n == k)
return true;
map<char, int> m;
for (char c : s)
m[c]++;
int odd = 0;
for (auto& it : m) {
odd += (it.second & 1);
}
return odd <= k;
}
};
main(){
Solution ob;
cout << (ob.canConstruct("true",4));
} อินพุต
"true"
ผลลัพธ์
1
