LeetCode-in-All
5. Longest Palindromic Substring
Medium
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad”
Output: “bab” Note: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Example 3:
Input: s = “a”
Output: “a”
Example 4:
Input: s = “ac”
Output: “a”
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
Solution
object Solution {
def longestPalindrome(s: String): String = {
val newStr = new Array[Char](s.length * 2 + 1)
newStr(0) = '#'
for (i <- 0 until s.length) {
newStr(2 * i + 1) = s.charAt(i)
newStr(2 * i + 2) = '#'
}
val dp = new Array[Int](newStr.length)
var friendCenter = 0
var friendRadius = 0
var lpsCenter = 0
var lpsRadius = 0
for (i <- 0 until newStr.length) {
dp(i) =
if (friendCenter + friendRadius > i)
Math.min(dp(friendCenter * 2 - i), (friendCenter + friendRadius) - i)
else
1
while (i + dp(i) < newStr.length
&& i - dp(i) >= 0
&& newStr(i + dp(i)) == newStr(i - dp(i))) {
dp(i) += 1
}
if (friendCenter + friendRadius < i + dp(i)) {
friendCenter = i
friendRadius = dp(i)
}
if (lpsRadius < dp(i)) {
lpsCenter = i
lpsRadius = dp(i)
}
}
s.substring((lpsCenter - lpsRadius + 1) / 2, (lpsCenter + lpsRadius - 1) / 2)
}
}