การหาคู่ index ของสตริงที่ต่อกันแล้วเป็น Palindrome ใน JavaScript

ปัญหา

หาคู่ index (i, j) ทั้งหมด ที่ concatenation ของ arr[i] + arr[j] เป็น palindrome

ตัวอย่าง

arr = ['tab', 'cat', 'bat']
output: [[0,2], [2,0]] ('battab', 'tabbat')

ตัวอย่างโค้ด

const arr = ['tab', 'cat', 'bat'];

const isPalindrome = (str = '') => {
  let i = 0;
  let j = str.length - 1;
  while (i < j) {
    if (str[i] != str[j]) return false;
    i++; j--;
  }
  return true;
};

const palindromePairs = (arr = []) => {
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (isPalindrome(arr[i] + arr[j])) {
        res.push([i, j]);
      }
      if (isPalindrome(arr[j] + arr[i])) {
        res.push([j, i]);
      }
    }
  }
  return res;
};

console.log(palindromePairs(arr));

ผลลัพธ์

[[0, 2], [2, 0]]

คำอธิบาย

Brute force O(n² * k) k = avg string length ตรวจสอบทุกคู่ (i,j) และ (j,i)

Optimization: ใช้ Trie หรือ Hash map ของ reversed strings เพื่อ O(n * k²)

LeetCode 336 Palindrome Pairs