LeetCode #5 Longest Palindromic Substring
Question
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
Solution
Approach #1
class Solution {
func longestPalindrome(_ s: String) -> String {
let arr = Array(s.utf16)
var start = 0
var end = 0
for i in 0..<arr.count {
expandAroundCenter(arr, left: i, right: i, start: &start, end: &end)
expandAroundCenter(arr, left: i, right: i + 1, start: &start, end: &end)
if end == arr.count - 1 { break }
}
let result = Array(arr[start...end])
return String(utf16CodeUnits: result, count: result.count)
}
func expandAroundCenter(_ arr: [UTF16.CodeUnit], left: Int, right: Int, start: inout Int, end: inout Int) {
if left < 0 || right >= arr.count || arr[left] != arr[right] { return }
var l = left
var r = right
while l >= 0, r < arr.count, arr[l] == arr[r] {
l -= 1
r += 1
}
l += 1
r -= 1
if r - l > end - start {
start = l
end = r
}
}
}
Time complexity: O(n^2).
Space complexity: O(1).
转载请注明出处:http://www.cnblogs.com/silence-cnblogs/p/6882592.html