最长公共子序列（LCS）代码运行报错：字符串索引越界求助

问题重现 #

实现最长公共子序列（Longest Common Subsequences, LCS）功能时，触发字符串索引越界错误，报错栈信息如下：

Traceback (most recent call last):
File "/home/runner/local/submission/main.py", line 149, in <module>
if test_case.execute(test_feedback):
File "/home/runner/local/submission/LCSTestCase.py", line 33, in execute
actual = user_matrix.get_longest_common_subsequences()
File "/home/runner/local/submission/LCSMatrix.py", line 60, in get_longest_common_subsequences
sequences = backtrack(self.row_count, self.column_count)
File "/home/runner/local/submission/LCSMatrix.py", line 49, in backtrack
elif str1[i - 1] == str2[j - 1]:
IndexError: string index out of range

当前实现的LCSMatrix类代码：

class LCSMatrix:
    def __init__(self, str1, str2):
        self.row_count = len(str1)
        self.column_count = len(str2)

        self.matrix = [[0] * (self.column_count + 1) for _ in range(self.row_count + 1)]
    
    # Populate the matrix using dynamic programming
        for i in range(1, self.row_count + 1):
            for j in range(1, self.column_count + 1):
                if str1[i - 1] == str2[j - 1]:
                    self.matrix[i][j] = self.matrix[i - 1][j - 1] + 1
                else:
                    self.matrix[i][j] = max(self.matrix[i - 1][j], self.matrix[i][j - 1])
                
                
# Returns the number of columns in the matrix, which also equals the length
# of the second string passed to the constructor.
    def get_column_count(self):
        return self.column_count

# Returns the matrix entry at the specified row and column indices, or 0 if
# either index is out of bounds.

    def get_entry(self, row_index, column_index):
    
        if 0 <= row_index <= self.row_count and 0 <= column_index <= self.column_count:
            matrix_made = self.matrix[row_index][column_index]
            return matrix_made
        else:
           return 0

# Returns the number of rows in the matrix, which also equals the length
# of the first string passed to the constructor.
     def get_row_count(self):
        return self.row_count

# Returns the set of distinct, longest common subsequences between the two
# strings that were passed to the constructor.
     def get_longest_common_subsequences(self):
    
        def backtrack(i, j):
            if i == 0 or j == 0:
                return {""}
            elif str1[i - 1] == str2[j - 1]:
                return {subseq + str1[i - 1] for subseq in backtrack(i - 1, j - 1)}
           else:
            sequences = set()
            if self.matrix[i - 1][j] >= self.matrix[i][j - 1]:
                sequences |= backtrack(i - 1, j)
            if self.matrix[i][j - 1] >= self.matrix[i - 1][j]:
                sequences |= backtrack(i, j - 1)
            return sequences

    str1 = str2 = ""
    sequences = backtrack(self.row_count, self.column_count)
    return sequences

问题分析 #

1. 核心错误：在get_longest_common_subsequences方法中，错误地将str1和str2重新赋值为空字符串str1 = str2 = ""，导致回溯函数backtrack访问str1[i-1]和str2[j-1]时，空字符串无对应索引，直接触发越界错误。
2. 实例属性缺失：__init__方法未将输入的str1和str2保存为实例属性，后续方法无法正确访问原始字符串。
3. 缩进错误：__init__中的DP矩阵填充循环缩进错误，不属于构造方法内；get_longest_common_subsequences内的代码缩进不符合Python规范，导致逻辑执行顺序错误。

修复后的代码 #

class LCSMatrix:
    def __init__(self, str1, str2):
        self.str1 = str1  # 保存原始字符串为实例属性
        self.str2 = str2
        self.row_count = len(str1)
        self.column_count = len(str2)

        self.matrix = [[0] * (self.column_count + 1) for _ in range(self.row_count + 1)]
    
        # 修正缩进：将DP填充逻辑放入__init__方法内
        for i in range(1, self.row_count + 1):
            for j in range(1, self.column_count + 1):
                if self.str1[i - 1] == self.str2[j - 1]:
                    self.matrix[i][j] = self.matrix[i - 1][j - 1] + 1
                else:
                    self.matrix[i][j] = max(self.matrix[i - 1][j], self.matrix[i][j - 1])
                
    # 返回矩阵列数（等于第二个输入字符串的长度）
    def get_column_count(self):
        return self.column_count

    # 返回指定行列的矩阵值，索引越界则返回0
    def get_entry(self, row_index, column_index):
        if 0 <= row_index <= self.row_count and 0 <= column_index <= self.column_count:
            return self.matrix[row_index][column_index]
        else:
           return 0

    # 返回矩阵行数（等于第一个输入字符串的长度）
    def get_row_count(self):
        return self.row_count

    # 返回两个字符串的所有不同最长公共子序列
    def get_longest_common_subsequences(self):
        def backtrack(i, j):
            if i == 0 or j == 0:
                return {""}
            # 使用实例属性访问原始字符串
            elif self.str1[i - 1] == self.str2[j - 1]:
                return {subseq + self.str1[i - 1] for subseq in backtrack(i - 1, j - 1)}
            else:
                sequences = set()
                if self.matrix[i - 1][j] >= self.matrix[i][j - 1]:
                    sequences |= backtrack(i - 1, j)
                if self.matrix[i][j - 1] >= self.matrix[i - 1][j]:
                    sequences |= backtrack(i, j - 1)
                return sequences

        # 移除错误的空字符串赋值，直接调用回溯函数
        sequences = backtrack(self.row_count, self.column_count)
        # 过滤出最长的子序列集合
        max_len = max(len(s) for s in sequences) if sequences else 0
        return {s for s in sequences if len(s) == max_len}

关键修改说明 #

1. 在__init__中新增self.str1 = str1和self.str2 = str2，将输入字符串保存为实例属性，确保后续方法能正确访问。
2. 修正__init__中DP填充循环的缩进，使其属于构造方法内的逻辑。
3. 删除get_longest_common_subsequences中错误的str1 = str2 = ""赋值语句。
4. 在回溯函数backtrack中，使用self.str1和self.str2访问原始字符串，避免索引越界。
5. 新增最长子序列过滤逻辑：返回的集合中只保留长度等于最大长度的子序列，处理无公共子序列的边界情况。

内容的提问来源于stack exchange，提问作者Haseeb Khan