เราได้รับสตริงและช่วงเริ่มจาก start ถึง end และภารกิจคือคำนวณจำนวนสตริงย่อยพาลินโดรมที่อยู่ในช่วงที่กำหนด สตริงพาลินโดรมคือสตริงที่เหมือนกันทั้งอ่านจากหน้าไปหลังและหลังไปหน้า เช่น nitin, aba ฯลฯ
ตัวอย่าง
Input - InputString = "cccaabbbdee", start = 2, end = 6;
Output - จำนวนสตริงย่อยพาลินโดรมในช่วงดัชนี 7
คำอธิบาย - เราได้รับช่วงและสตริง ดังนั้นเราจะเริ่มเดินทางผ่านสตริงจากตัวชี้ start ซึ่งคือ 2 คือ 'c' จนถึง 6 คือ 'b' ดังนั้น substring คือ 'caabb' สตริงย่อยพาลินโดรมคือ 'c', 'a', 'a', 'b', 'b', 'aa' และ 'bb' ดังนั้นจำนวนสตริงย่อยพาลินโดรมคือ 7
Input - InputString = "lioaabbbdee", start = 0, end = 2;
Output - จำนวนสตริงย่อยพาลินโดรมในช่วงดัชนี 3
คำอธิบาย - เราได้รับช่วงและสตริง ดังนั้นเราจะเริ่มเดินทางผ่านสตริงจากตัวชี้ start ซึ่งคือ 0 คือ 'l' จนถึง 2 คือ 'o' ดังนั้น substring คือ 'lio' สตริงย่อยพาลินโดรมคือ 'l', 'i' และ 'o' ดังนั้นจำนวนสตริงย่อยพาลินโดรมคือ 3
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- ประกาศสตริงขนาดที่กำหนดและช่วงเริ่มจากตัวแปร start ถึง end
- ส่งข้อมูลให้ฟังก์ชันชื่อ palindrome_index(arr, InputString) เพื่อประมวลผลต่อ
- ภายในฟังก์ชัน ประกาศอีกอาร์เรย์ชื่อ checked ด้วยขนาดอาร์เรย์
- เริ่มลูป FOR i จาก 0 ถึงความยาวของอาร์เรย์
- ภายในลูป เริ่มลูป FOR อีกทีจาก j จาก 0 ถึงความยาวของอาร์เรย์
- ภายในลูป ตั้ง check[i][j] = 0 และ arr[i][j] = 0
- เริ่มลูป FOR i จาก length - 1 ถึง i >= 0
- ภายในลูป ตั้ง check และ arr ของ i เป็น 1 แล้วเริ่มลูป FOR อีกทีจาก j = i + 1 ถึงความยาวของอาร์เรย์
- ภายในลูป ตรวจสอบ IF สตริงที่ i เท่ากับสตริงที่ j AND (i + 1 > j - 1 OR check[i + 1][j - 1] != 0) แล้วตั้ง check[i][j] = 1 ELSE ตั้ง check[i][j] = 0 แล้วตั้ง arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j]
- พิมพ์อาร์เรย์ 2D เป็น start และ end
ตัวอย่าง
import java.io.*;
class testqwe {
static void palindrome_index(int arr[][], String s) {
int length = s.length();
int[][] check = new int[length + 1][length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= length; j++) {
check[i][j] = 0;
arr[i][j] = 0;
}
}
for (int i = length - 1; i >= 0; i--) {
check[i][i] = arr[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
check[i][j] = 1;
} else {
check[i][j] = 0;
}
arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
}
}
}
public static void main(String args[]) {
String InputString = "cccaabbbdee";
int[][] arr;
arr = new int[50][50];
palindrome_index(arr, InputString);
int start = 2;
int end = 6;
System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
}
}
หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Count of Palindromic substrings in an Index range 7
