5. Longest Palindromic Substring

[NaClYen]

5. Longest Palindromic Substring

Given a string s, return the longest

palindromic

substring

in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

[NaClYen]

go - 1

CPU: 144ms Memory: 2.5Mb

中途一直想往最佳解, 但一直困住... 最後還是先回頭寫比較直觀的雙層迴圈模式 🤣 golang 的 string 操作到底是太強還是沒有被偵測到呢...?

func isPal(s string) (palStr string) {
    // fmt.Printf("isPal, [%s]\n", s)

    // 最後一個字元
    if len(s) == 1 {
        return s
    }

    firstByte := s[0]
    lastByte := s[len(s)-1]

    // fmt.Printf("%c == %c ? %t\n", firstByte, lastByte, firstByte == lastByte)

    if firstByte == lastByte {
        // 最後兩個字元
        if len(s) == 2 {
            return s
        }

        // 繼續向內檢測
        if isPal(s[1:len(s)-1]) != "" {
            return s
        } else {
            return ""
        }
    } else {
        return ""
    }
}

func longestPalindrome(s string) string {
    checkFn := isPal
    maxStr := ""

    updateMax := func(target string) {
        if len(target) > len(maxStr) {
            maxStr = target
        }
    }

    for i := range s {
        offLeft := s[i:]

        // early return
        if len(offLeft) < len(maxStr) {
            break
        }

        for j := range offLeft {
            curS := offLeft[:len(offLeft)-j]

            // early return
            if len(curS) < len(maxStr) {
                break
            }

            if r := checkFn(curS); r != "" {
                updateMax(curS)
            }

            // fmt.Printf("%s\n", curS)
        }
    }

    // return fmt.Sprintf("%c", s[0])
    return maxStr
}

[NaClYen]

go - 2

CPU: 58ms Memory: 2.3MB

修改自前一個版本, 不使用遞迴 & updateMax

func isPal(s string) (result bool) {
    // round++
    // fmt.Printf("isPal, [%s]\n", s)

    // 最後一個字元
    if len(s) == 1 {
        return true
    }

    left := 0
    right := len(s)

    for right > left {
        if s[left] != s[right-1] {
            return false
        }
        left++
        right--
    }

    return true
}

func longestPalindrome(s string) string {
    maxStr := ""

    for i := range s {
        offLeft := s[i:]

        // early break
        if len(offLeft) < len(maxStr) {
            break
        }

        for j := range offLeft {
            curS := offLeft[:len(offLeft)-j]

            // early break
            if len(curS) < len(maxStr) {
                break
            }

            if isPal(curS) {
                // 因為前面的 early break, 這裡的 curS 長度必然大於 maxStr
                maxStr = curS
            }

            // fmt.Printf("%s\n", curS)
        }
    }

    // return fmt.Sprintf("%c", s[0])
    return maxStr
}