การหาคู่ดัชนีที่ต่อกันเป็นพาลินโดรมใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์คำที่ไม่ซ้ำกัน ฟังก์ชันควรคืนค่าอาร์เรย์ของคู่ดัชนีทั้งหมด ที่คำในคู่นั้นต่อกันแล้วได้พาลินโดรม (palindrome)

ตัวอย่าง

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

const arr = ["abcd", "dcba", "lls", "s", "sssll"];
const findPairs = (arr = []) => {
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j) {
        let k = `${arr[i]}${arr[j]}`;
        let l = [...k].reverse().join('');
        if (k === l) res.push([i, j]);
      }
    }
  }
  return res;
};
console.log(findPairs(arr));

ผลลัพธ์

[ [ 0, 1 ], [ 1, 0 ], [ 2, 4 ], [ 3, 2 ] ]

คำอธิบายเพิ่มเติม

อัลกอริทึมแบบ brute force O(n²×k) โดย k = ความยาวคำ สามารถปรับปรุงได้ด้วย Trie หรือ Hash map เพื่อลดเป็น O(n×k²) โดยตรวจสอบ prefix/suffix ที่เป็นพาลินโดรม