Note: study again
(s string)
| 50 | |
| 51 | // Note: study again |
| 52 | func longestPalindrome0(s string) string { |
| 53 | if len(s) < 1 { |
| 54 | return "" |
| 55 | } |
| 56 | |
| 57 | // For each index in s, expand as much as possible at every center |
| 58 | // in the string. There are n * 2 - 1 centers of possible palindromes in s. |
| 59 | // That is true because there is a center at every index i and a center |
| 60 | // in between every two indices i and j. |
| 61 | start := 0 |
| 62 | end := 0 |
| 63 | for i := 0; i < len(s); i++ { |
| 64 | len1 := expandAroundCenter(s, i, i) |
| 65 | len2 := expandAroundCenter(s, i, i+1) |
| 66 | maxLen := int(math.Max(float64(len1), float64(len2))) |
| 67 | |
| 68 | // If the maxLen from the last iteration is longer in length |
| 69 | // than the longest palindromic substring seen so far. |
| 70 | if maxLen > end-start { |
| 71 | // Calculate the starting index of the longest substring so far |
| 72 | // by: |
| 73 | // 1. subtract 1 from the maxLen that was expanded from the center |
| 74 | // 2. divide that value by 2 |
| 75 | // 3. subtract that value from i |
| 76 | |
| 77 | // Example: |
| 78 | // 01234 |
| 79 | // babad |
| 80 | // i |
| 81 | |
| 82 | // Minus one on maxLen for even number palindromes |
| 83 | // 0123 |
| 84 | // abba |
| 85 | |
| 86 | // i = 2, maxLen = 3 |
| 87 | // start = i - ((maxLen - 1) / 2) |
| 88 | // start = 2 - ((3 - 1) / 2) |
| 89 | // start = 1 |
| 90 | start = i - ((maxLen - 1) / 2) |
| 91 | end = i + (maxLen / 2) |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | // return the substring from start to end (+1 for non-inclusive substring) |
| 96 | return s[start : end+1] |
| 97 | } |
| 98 | |
| 99 | func expandAroundCenter(s string, left int, right int) int { |
| 100 | // The left and right values are either: |