Buổi 1: Longest Palindromic Substring ( tìm chuổi con đối xứng có độ dài dài nhất)
Given a string
s
, return
the longest palindromic substring
in
s
.
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: s = "cbbd"
Output: "bb"
Input: s = "a"
Output: "a"
Input: s = "ac"
Output: "a"
- liệt kê tất cả các chuổi con có độ dài lớn hơn hoặc bằng 2,
- kiểm tra tính đối xứng của chuổi con đó
- xử lý các trường hợp đặc biệt
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (s.length < 2) {
return s[0]
}
let result = ''
for (let i = 0; i < s.length; i++) {
for (let j = i + 2; j <= s.length; j ++) {
const subStr = s.substring(i, j)
if (check(subStr) && result.length < subStr.length) {
result = subStr
}
}
}
if (result ==='') {
return s[0]
}
return result
};
function check(s) {
if (s.length < 2) {
return true
}
const haftLength = Math.floor(s.length/2)
for (let i = 0 ; i < haftLength; i++) {
const j = s.length - 1 - i
if (s[i] !== s[j]) {
return false
}
}
return true
}
