Hackerrank Common Child（LCS）问题解法超时，寻求优化思路

我正在解决Hackerrank上的Common Child问题，它本质就是**最长公共子序列（LCS）**问题。

我尝试了如下解法：

def commonChild(s1, s2):
    LCS_table = [[0 for _ in range(len(s2)+1)] 
                 for _ in range(len(s1)+1)
                ]              
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):            
            if s1[i-1] == s2[j-1]: #注意这里不能用[i]和[j]，而是[i-1]和[j-1]
                LCS_table[i][j] = LCS_table[i-1][j-1] + 1
            else:
                LCS_table[i][j] = max(LCS_table[i-1][j], LCS_table[i][j-1])
    return LCS_table[-1][-1]

该解法通过了8个测试用例，但有6个测试用例出现超时错误。我找了一些参考解法尝试：

解法2 #

def commonChild(a, b):
    m = len(a)
    n = len(b)
    prev = [0 for x in range(n + 1)]
    for i in range(1, m + 1):
        curr = [0 for x in range(n + 1)]
        for j in range(1, n + 1):
            curr[j] = max(prev[j], curr[j - 1])
            if a[i - 1] == b[j - 1]:
                curr[j] = max(curr[j], prev[j - 1] + 1)
        prev = curr
    return curr[n]

解法3 #

def commonChild(s1, s2):
    m = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
    for i,c in enumerate(s1,1):
        for j,d in enumerate(s2,1):
            if c == d:
                m[i][j] = m[i-1][j-1]+1
            else:
                m[i][j] = max(m[i][j-1],m[i-1][j])
                   
    return m[-1][-1]

但这些参考解法也仅能通过半数测试用例，其余仍超时。请问是否存在更高效的优化思路？

1. 单一维数组的空间优化（减少内存开销） #

解法2已经用了滚动数组，但可以进一步优化为仅用一个一维数组，避免频繁创建新列表的开销。通过保存前值的方式，覆盖旧状态而不影响计算：

def commonChild(s1, s2):
    n = len(s2)
    dp = [0] * (n + 1)
    for c in s1:
        prev_val = 0  # 保存dp[j-1]的原始值，防止被覆盖
        for j in range(1, n + 1):
            temp = dp[j]
            if c == s2[j-1]:
                dp[j] = prev_val + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            prev_val = temp
    return dp[-1]

这种方式仅维护一个数组，减少了内存分配和回收的耗时，在Python中能显著提升循环效率。

2. 基于二分查找的O(n log m)优化 #

当字符串长度较大（如1e5级别）时，O(nm)的算法必然超时。此时可以将LCS问题转化为**最长递增子序列（LIS）**问题，通过二分查找将时间复杂度降至O(n log m)：

1. 预处理第二个字符串，记录每个字符出现的所有位置（按顺序存储）。
2. 遍历第一个字符串的每个字符，在对应字符的位置列表中，用二分查找找到第一个大于当前最后匹配位置的索引，构建递增序列。

代码实现：

import bisect

def commonChild(s1, s2):
    # 预处理s2，记录每个字符的位置列表
    char_positions = {}
    for idx, char in enumerate(s2):
        if char not in char_positions:
            char_positions[char] = []
        char_positions[char].append(idx)
    
    # 构建递增序列，用二分查找优化
    lis = []
    for char in s1:
        if char not in char_positions:
            continue
        # 逆序遍历位置，确保能找到最适合的插入点
        for pos in reversed(char_positions[char]):
            insert_idx = bisect.bisect_left(lis, pos)
            if insert_idx == len(lis):
                lis.append(pos)
            else:
                lis[insert_idx] = pos
    return len(lis)

这个方法能轻松通过Hackerrank的大尺寸测试用例。

3. 边界情况剪枝 #

提前处理一些特殊情况，避免不必要的计算：

• 如果两个字符串的字符集合没有交集，直接返回0。
• 如果其中一个字符串是另一个的子序列，直接返回较短字符串的长度。

4. 环境层面优化 #

• 使用PyPy代替Python运行代码：PyPy的JIT编译对循环密集型代码的加速效果非常明显，很多O(nm)的解法在PyPy下可以通过所有测试用例。
• 用array模块代替列表存储dp数组，减少内存占用并提升访问速度。

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