ในบทช่วยสอนนี้ เราต้องแก้ปัญหาการสืบค้นสตริงย่อยแบบพาลินโดรมของสตริงที่กำหนด การแก้ปัญหาการสืบค้นสตริงย่อยแบบพาลินโดรมซับซ้อนกว่าการสืบค้นทั่วไปใน C++ มาก ต้องใช้โค้ดและตรรกะที่ซับซ้อนกว่า
ในบทช่วยสอนนี้ เราได้รับสตริง str และจำนวน Q คำสืบค้นสตริงย่อย[L...R] แต่ละคำมีค่า L และ R เราต้องเขียนโปรแกรมแก้คำสืบค้นว่าสตริงย่อย[L...R] เป็นพาลินโดรมหรือไม่ เราต้องตัดสินใจว่าสตริงย่อยที่เกิดขึ้นในช่วง L ถึง R เป็นพาลินโดรมหรือไม่สำหรับแต่ละคำสืบค้น ตัวอย่างเช่น:
ให้ป้อน "abbbabaaaba" เป็นสตริงนำเข้า คำสืบค้นคือ [3, 13], [3, 11], [5, 8], [8, 12] ต้องกำหนดว่าสตริงย่อยเป็นพาลินโดรมหรือไม่ "abaaabaaaba" (3, 13) เป็นพาลินโดรม "baaa" [3, 11] ไม่สามารถเป็นพาลินโดรมได้ [5, 8]: "aaab" ไม่สามารถเป็นพาลินโดรมได้ มีพาลินโดรมใน "baaab" ([3, 12])
แนวทางการหาคำตอบ
วิธี Naive (ตรวจสอบโดยตรง)
ที่นี่ เราต้องหาพาลินโดรมโดยตรวจสอบว่าสตริงย่อยจากช่วงดัชนี L ถึง R เป็นพาลินโดรมหรือไม่ ดังนั้นเราต้องตรวจสอบคำสืบค้นทีละคำ และตัดสินใจว่าเป็นพาลินโดรมหรือไม่ เนื่องจากมี Q คำสืบค้น และแต่ละคำใช้เวลา O(N) ในการตอบ ในกรณีแย่สุดใช้เวลา O(Q.N)
ตัวอย่างโค้ด (วิธี Naive)
#include <bits/stdc++.h> using namespace std; int isPallindrome(string str){ int i, length; int flag = 0; length = str.length(); for(i=0;i < length ;i++){ if(str[i] != str[length-i-1]) { flag = 1; break; } } if (flag==1) return 1; return 0; } void solveAllQueries(string str, int Q, int query[][2]){ for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"Palindrome\n":cout<<"Not palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveAllQueries(str, Q, query); return 0; }
ข้อมูลส่งออก
Palindrome Palindrome Not palindrome!
วิธี Dynamic Programming
การใช้แนวทาง Dynamic Programming เป็นตัวเลือกที่มีประสิทธิภาพ ในการแก้ปัญหา เราต้องสร้างอาร์เรย์ DP ซึ่งเป็นอาร์เรย์ 2 มิติที่มีค่า boolean บ่งบอกว่าสตริงย่อย[i...j] เป็นพาลินโดรมสำหรับ DP[i][j]
สร้างเมทริกซ์ DP นี้ และตรวจสอบค่า L-R สำหรับแต่ละคำสืบค้น
ตัวอย่างโค้ด (Dynamic Programming)
#include <bits/stdc++.h> using namespace std; void computeDP(int DP[][50], string str){ int length = str.size(); int i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) DP[i][j] = 0; } for (j = 1; j <= length; j++) { for (i = 0; i <= length - j; i++) { if (j <= 2) { if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = 1; } else if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = DP[i + 1][i + j - 2]; } } } void solveAllQueries(string str, int Q, int query[][2]){ int DP[50][50]; computeDP(DP, str); for(int i = 0; i < Q; i++){ DP[query[i][0] - 1][query[i][1] - 1]?cout <<"not palindrome!\n":cout<<"palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveAllQueries(str, Q, query); return 0; }
ข้อมูลส่งออก
palindrome! not palindrome! palindrome!
สรุป
ในบทช่วยสอนนี้ เราเรียนรู้วิธีแก้ปัญหาการสืบค้นสตริงย่อยแบบพาลินโดรมพร้อมโค้ด C++ สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ โค้ดนี้เป็นหนึ่งในโค้ดที่ซับซ้อนและยาวที่สุด การสืบค้นพาลินโดรมยากกว่าการสืบค้นสตริงย่อยทั่วไป และต้องการตรรกะที่แม่นยำมาก หวังว่าบทช่วยสอนนี้จะมีประโยชน์
