การนับลำดับย่อยพาลินโดรมที่เป็นไปได้ทั้งหมดภายในสตริงใน JavaScript

ลำดับพาลินโดรม:

ลำดับสตริงเรียกว่าลำดับพาลินโดรมหากอ่านจากด้านหน้าและด้านหลังเหมือนกัน ตัวอย่างเช่น 'aba', 'madam, 'did' เป็นลำดับ palindrome ที่ถูกต้องทั้งหมด

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับสตริงเป็นอาร์กิวเมนต์แรกและอาร์กิวเมนต์เดียว สตริงที่ใช้เป็นอินพุตรับประกันว่าประกอบด้วย 'a', 'b', 'c' และ 'd' เท่านั้น ฟังก์ชันของเราควรนับและส่งคืนจำนวนลำดับย่อยของ palindrome ที่ต่อเนื่องกันหรือไม่ต่อเนื่องกันที่ปรากฏในสตริง

ตัวอย่างเช่น −

หากสตริงอินพุตเป็น −

const str = 'bccb';

จากนั้นผลลัพธ์ควรเป็น −

const output = 6;

เพราะสตริงพาลินโดรมที่นี่คือ 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

const str = 'bccb';
const countPalindromes = (str = '') => {
   let base = 1000000007;
   const dp = Array(str.length).fill([]);
   for (let l = 1; l <= str.length; l ++) {
      for (let i = 0; i + l - 1 < str.length; i ++) {
         let j = i + l - 1;
         if (l === 1) {
            dp[i][j] = 1;
            continue;
         }
         if (l === 2) {
            dp[i][j] = 2;
            continue;
         }
         if (str[i] === str[j]) {
            let left = i + 1, right = j - 1;
            while (left <= right && str[left] != str[i]) {
               left ++;
            }
            while (left <= right && str[right] != str[i]) {
               right --;
            }
            if (left > right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
            }
            else if (left === right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
            } else {
               dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
            }
         } else {
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
         }
         dp[i][j] = dp[i][j] < 0? dp[i][j] + base : dp[i][j] % base;
      }
   }
   return dp[0][str.length - 1];
};
console.log(countPalindromes(str));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

6