นับ subsequence แบบพาลินโดรมทั้งหมดในสตริงด้วย JavaScript

พาลินโดรม (Palindrome)

ลำดับตัวอักษรที่อ่านจากหน้าหรือหลังได้เหมือนกัน เช่น 'aba', 'madam', 'did'

ปัญหา

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

ตัวอย่าง

const str = 'bccb';

ผลลัพธ์: 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