ในบทช่วยสอนนี้ เราจำเป็นต้องแก้ไขการสืบค้นสตริงย่อย palindrome ของสตริงที่กำหนด การแก้ไขข้อความค้นหาสตริงย่อย palindrome นั้นซับซ้อนกว่าการแก้ไขการสืบค้นปกติใน C ++ ต้องใช้โค้ดและตรรกะที่ซับซ้อนกว่านี้มาก
ในบทช่วยสอนนี้ เราจัดเตรียมข้อความค้นหาสตริง str และหมายเลข Q ของสตริงย่อย[L...R] โดยแต่ละรายการมีค่า L และ R สองค่า เรามุ่งหวังที่จะเขียนโปรแกรมที่จะแก้ปัญหาการสืบค้นข้อมูลเพื่อระบุว่าสตริงย่อย[L. ..R] เป็นพาลินโดรม เราต้องตัดสินใจว่าสตริงย่อยที่สร้างขึ้นภายในช่วง L ถึง R เป็นพาลินโดรมเพื่อแก้ปัญหาแต่ละรายการหรือไม่ ตัวอย่างเช่น −
Let's input "abbbabaaaba" as our input string. The queries were [3, 13], [3, 11], [5, 8], [8, 12] It is necessary to determine whether the substring is a plaindrome A palindrome is "abaaabaaaba" (3, 13) . It is not possible to write "baaa" as a palindrome [3, 11]. As in [5, 8]: "aaab" cannot be a palindrome. There is a palindrome in "baaab" ([3, 12]).
แนวทางในการหาแนวทางแก้ไข
วิธีการไร้เดียงสา
ที่นี่ เราต้องหาพาลินโดรมโดยตรวจสอบว่าสตริงย่อยมาจากช่วงดัชนี L ถึง R หรือไม่ ดังนั้น เราจำเป็นต้องตรวจสอบการค้นหาสตริงย่อยทั้งหมดทีละรายการและพิจารณาว่าเป็นพาลินโดรมหรือไม่ เนื่องจากมีการสืบค้น Q และแต่ละการสืบค้นจะใช้เวลา 0(N) ในการตอบ ในกรณีที่เลวร้ายที่สุดจะใช้เวลา 0(Q.N)
ตัวอย่าง
#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!
วิธีการเขียนโปรแกรมแบบไดนามิก
การใช้แนวทางการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหาเป็นตัวเลือกที่มีประสิทธิภาพ ในการแก้ปัญหา เราจะต้องสร้างอาร์เรย์ DP ซึ่งเป็นอาร์เรย์สองมิติที่มีค่าบูลีนที่ระบุว่าสตริงย่อย[i...j] เป็นพาลินโดรมสำหรับ DP[i][j] หรือไม่
เมทริกซ์ DP นี้จะถูกสร้างขึ้น และค่า LR ทั้งหมดสำหรับแต่ละแบบสอบถามจะถูกตรวจสอบ
ตัวอย่าง
#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!
บทสรุป
ในบทช่วยสอนนี้ เราได้เรียนรู้วิธีแก้ไขการสืบค้นสตริงย่อย palindrome พร้อมกับโค้ด c++ เรายังเขียนโค้ดนี้ในภาษาจาวา ไพธอน และภาษาอื่นๆ ได้ด้วย รหัสนี้เป็นหนึ่งในรหัสที่ซับซ้อนและยาวที่สุด ข้อความค้นหา Palindrome นั้นยากกว่าการสืบค้นสตริงย่อยทั่วไป และต้องใช้ตรรกะที่แม่นยำมาก เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
