Lintcode最长回文子串问题求助：Python新手遇索引越界错误

Hey there! Let's break down that error you're seeing and fix it step by step.

First, let's unpack the error message: IndexError: string index out of range on the line while k[0] == k[-1]:. This happens because at some point in your ispalindrome function, you're trying to access the first (k[0]) and last (k[-1]) characters of an empty string—which has no characters to index, hence the error.

Why does this happen? #

Chances are your ispalindrome function looks something like this:

def ispalindrome(k):
    while k[0] == k[-1]:
        k = k[1:-1]  # Trim first and last characters
    return len(k) == 0

Let's walk through what happens with a string like "aa":

1. First loop iteration: k[0] and k[-1] are both 'a', so we trim k to "" (empty string).
2. Next loop iteration: The code tries to check k[0] and k[-1] again, but an empty string has no indices to access—boom, the IndexError hits.

Fixing the ispalindrome function #

We need to add a guard clause to ensure we only compare characters when the string has at least 2 characters left. Here's a corrected version:

def ispalindrome(k):
    # Only enter the loop if the string is long enough AND first/last chars match
    while len(k) > 1 and k[0] == k[-1]:
        k = k[1:-1]
    # If what's left is length 0 or 1, it's a valid palindrome
    return len(k) <= 1

Alternatively, a more efficient (and easier to debug) approach uses two pointers to check the palindrome without modifying the string:

def ispalindrome(k):
    left = 0
    right = len(k) - 1
    while left < right:
        if k[left] != k[right]:
            return False
        left += 1
        right -= 1
    return True

This method avoids index issues entirely because we stop the loop as soon as left meets right.

Bonus: A Complete Working Solution #

If you're using a brute-force approach (checking all possible substrings), here's a full, error-free example with the fixed palindrome check:

def longestPalindrome(s):
    n = len(s)
    if n <= 1:
        return s
    
    max_length = 1
    longest_sub = s[0]
    
    # Iterate over all possible starting indices
    for i in range(n):
        # Iterate over all possible ending indices (from i onwards)
        for j in range(i + 1, n):
            current_sub = s[i:j+1]
            if ispalindrome(current_sub) and len(current_sub) > max_length:
                max_length = len(current_sub)
                longest_sub = current_sub
    
    return longest_sub

def ispalindrome(k):
    left = 0
    right = len(k) - 1
    while left < right:
        if k[left] != k[right]:
            return False
        left += 1
        right -= 1
    return True

This will correctly find the longest palindromic substring without throwing index errors.

内容的提问来源于stack exchange，提问作者Greedy.W