การใช้งาน Longest palindrome in string ในภาษา Lua แบบง่ายๆ พร้อมตัวอย่าง

บทนำ

การเขียนโปรแกรมนั้นเป็นศาสตร์และศิลป์ที่ท้าทาย ซึ่งผู้เรียนต้องใช้ทั้งความรู้เชิงตรรกะและความคิดสร้างสรรค์ในการแก้ปัญหา หนึ่งในปัญหาทางคอมพิวเตอร์ที่น่าสนใจคือการค้นหา "Longest Palindrome in a String" หรือในภาษาไทยคือการค้นหาพาลินโดรมที่ยาวที่สุดในสตริง ซึ่งก็คือคำหรือวลีที่อ่านแล้วยังคงเหมือนเดิมไม่ว่าจะอ่านจากหน้าไปหลังหรือจากหลังมาหน้า ในบทความนี้ เราจะมาทำความเข้าใจและทดลองเขียนโค้ดเพื่อแก้ปัญหานี้ในภาษาโปรแกรมมิ่ง Lua ซึ่งเป็นภาษาที่มีเอกลักษณ์ พร้อมทั้งนำเสนอ usecase ในโลกจริงและไม่ลืมที่จะเชิญชวนผู้อ่านมาศึกษาการเขียนโปรแกรมกับเราที่ EPT!

การค้นหา Longest Palindrome in a String

ตัวอย่างโค้ดที่ 1: การใช้งาน Brute Force

 function isPalindrome(s)
  return s == string.reverse(s)
end

function longestPalindrome(s)
  local maxPal = ""
  local len = string.len(s)
  for i = 1, len do
    for j = i, len do
      local subStr = string.sub(s, i, j)
      if isPalindrome(subStr) and string.len(subStr) > string.len(maxPal) then
        maxPal = subStr
      end
    end
  end
  return maxPal
end

print(longestPalindrome("babad"))

ในตัวอย่างข้างต้น เราใช้วิธี brute force ซึ่งเป็นวิธีที่เรียบง่ายที่สุดแต่ก็ใช้เวลาทำงานมากเมื่อเจอกับสตริงที่มีขนาดใหญ่ เริ่มจากการสร้างฟังก์ชัน `isPalindrome` เพื่อตรวจสอบว่าสตริงที่เราต้องการนั้นเป็นพาลินโดรมหรือไม่ และจากนั้นทำการค้นทุกความยาวที่เป็นไปได้ของ substring ใน `longestPalindrome` และเก็บพาลินโดรมที่ยาวที่สุดไว้

ตัวอย่างโค้ดที่ 2: Dynamic Programming

 function longestPalindromeDP(s)
  local n = string.len(s)
  local dp = {}
  for i = 1, n do
    dp[i] = {}
    for j = 1, n do
      dp[i][j] = false
    end
  end
  local maxPal = ""

  for i = n, 1, -1 do
    for j = i, n do
      dp[i][j] = (s:sub(i, i) == s:sub(j, j)) and (j - i < 3 or dp[i + 1][j - 1])
      if dp[i][j] and j - i + 1 > string.len(maxPal) then
        maxPal = s:sub(i, j)
      end
    end
  end

  return maxPal
end

print(longestPalindromeDP("cbbd"))

อัลกอริทึม Dynamic Programming (DP) นี้จะเหมาะกับพาลินโดรมที่มีขนาดใหญ่เพราะมันใช้เวลาน้อยกว่าวิธี brute force โค้ดนี้ใช้ตาราง dp ในการเก็บประวัติการตรวจสอบพาลินโดรมที่ย่อย ซึ่งช่วยลดจำนวนการตรวจสอบครั้งที่ไม่จำเป็น

ตัวอย่างโค้ดที่ 3: Expand Around Center

 function expand(s, left, right)
  local L, R = left, right
  while L >= 1 and R <= string.len(s) and s:sub(L, L) == s:sub(R, R) do
    L = L - 1
    R = R + 1
  end
  return string.sub(s, L + 1, R - 1)
end

function longestPalindromeCenter(s)
  if s == nil or string.len(s) == 0 then return "" end
  local maxPal = ""
  for i = 1, string.len(s) do
    local p1 = expand(s, i, i) -- Assume odd length, try to extend Palindrome as possible
    local p2 = expand(s, i, i + 1) -- Assume even length.
    local p = string.len(p1) > string.len(p2) and p1 or p2
    maxPal = string.len(p) > string.len(maxPal) and p or maxPal
  end
  return maxPal
end

print(longestPalindromeCenter("ac"))

โค้ดนี้ใช้เทคนิค "Expand Around Center" ซึ่งเราจะรับช่วงกลางของพาลินโดรมที่เป็นไปได้และขยายเข้าไปตามทั้งสองทิศทาง เทคนิคนี้ทำให้สามารถค้นหาพาลินโดรมที่มีความยาวคี่และคู่ได้อย่างรวดเร็ว

Usecase ในโลกจริง

การค้นหาพาลินโดรมที่ยาวที่สุดนั้นไม่ได้มีประโยชน์แค่ในโลกของคณิตศาสตร์หรือการแข่งขันเขียนโปรแกรมเท่านั้น แต่ยังใช้ในการวิเคราะห์ลำดับ DNA ในชีววิทยาคำนวณ เพื่อทำความเข้าใจกับโครงสร้างของ DNA ที่มีคุณสมบัติเป็นพาลินโดรม นอกจากนี้ในด้านเข้ารหัสข้อมูล (Cryptography) การค้นหาพาลินโดรมอาจมีการใช้งานเพื่อวิเคราะห์และสร้างรหัสความปลอดภัย

สรุปและการเชิญชวน

พาลินโดรมไม่เพียงแค่เป็นปรากฏการณ์ทางภาษาที่น่าสนใจเท่านั้น แต่ยังเป็นแนวทางในการพัฒนาทักษะตรรกะและการเขียนโปรแกรมของเรา หากคุณมีความสนใจในการขุดลึกลงไปในศาสตร์แห่งโค้ดและต้องการเรียนรู้วิธีการแก้ปัญหาระดับสูง เราขอเชิญคุณมาเรียนรู้และพัฒนาทักษะการเขียนโปรแกรมกับเราที่ EPT ที่นี่เรามีหลักสูตรและโปรแกรมการสอนที่ครอบคลุมหลายภาษา รวมถึงให้คำปรึกษาและแนะนำวิธีปฏิบัติที่ดีที่สุดในวงการไอที ร่วมกับเราและเป็นส่วนหนึ่งของโปรแกรมเมอร์ยุคใหม่ที่พร้อมจะก้าวข้ามทุกขีดจำกัดไปด้วยกัน!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง