Java递归函数如何避免全局外部变量——以最长公共序列实现为例

Great question—relying on global or external variables for collecting results like this is definitely a bad practice (as you noted, it scales terribly when you have multiple functions doing similar work). Let’s walk through a few clean, maintainable ways to fix your allPaths function so it doesn’t depend on external state.

1. Pass the result list as a mutable parameter #

Since lists are mutable in Python, you can pass your result collection list directly into the allPaths function. The function will modify the list in-place, no external variables required. This keeps the function self-contained and reusable.

Here’s how you’d refactor the code:

def allPaths(i, j, s1, s2, dp, current, lcs_list):
    # Base case: reach the start of either string
    if i == 0 or j == 0:
        lcs_list.append(current[::-1])
        return
    
    # If characters match, move diagonally back
    if s1[i-1] == s2[j-1]:
        current.append(s1[i-1])
        allPaths(i-1, j-1, s1, s2, dp, current, lcs_list)
        current.pop()  # Backtrack
    else:
        # Move in the direction of the longer sub-sequence
        if dp[i-1][j] == dp[i][j]:
            allPaths(i-1, j, s1, s2, dp, current, lcs_list)
        if dp[i][j-1] == dp[i][j]:
            allPaths(i, j-1, s1, s2, dp, current, lcs_list)

To use this, initialize the list where you call the function, then pass it in:

def find_all_lcs(s1, s2):
    # First compute the DP table (standard LCS length logic)
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Collect all LCS paths
    lcs_list = []
    allPaths(m, n, s1, s2, dp, [], lcs_list)
    
    # Remove duplicates (if needed) and return results
    unique_lcs = list(set(lcs_list))
    lcs_length = len(unique_lcs[0]) if unique_lcs else 0
    return lcs_length, unique_lcs

2. Return collected paths directly (functional style) #

If you prefer a side-effect-free approach (no in-place modifications), have allPaths return a list of paths instead of modifying an external one. Each recursive call builds and returns its own set of paths, which you combine at higher levels.

Here’s the refactored function:

def allPaths(i, j, s1, s2, dp, current):
    if i == 0 or j == 0:
        return [current[::-1]]
    
    paths = []
    if s1[i-1] == s2[j-1]:
        current.append(s1[i-1])
        paths.extend(allPaths(i-1, j-1, s1, s2, dp, current))
        current.pop()
    else:
        if dp[i-1][j] == dp[i][j]:
            paths.extend(allPaths(i-1, j, s1, s2, dp, current))
        if dp[i][j-1] == dp[i][j]:
            paths.extend(allPaths(i, j-1, s1, s2, dp, current))
    return paths

Call it like this:

def find_all_lcs(s1, s2):
    # Compute DP table (same as before)
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    lcs_list = allPaths(m, n, s1, s2, dp, [])
    unique_lcs = list(set(lcs_list))
    lcs_length = len(unique_lcs[0]) if unique_lcs else 0
    return lcs_length, unique_lcs

This approach is more aligned with functional programming principles, making the function easier to test and reason about (no hidden state changes).

3. Encapsulate logic in a class (for larger codebases) #

If you have multiple functions related to LCS processing (not just allPaths), wrapping everything in a class keeps state like the DP table and input strings contained within an instance. This avoids global variables entirely and makes your code more modular.

Example implementation:

class LCSProcessor:
    def __init__(self, s1, s2):
        self.s1 = s1
        self.s2 = s2
        self.dp = self._compute_dp_table()
    
    def _compute_dp_table(self):
        # Private method to build the DP table
        m, n = len(self.s1), len(self.s2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if self.s1[i-1] == self.s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp
    
    def _all_paths(self, i, j, current):
        # Private recursive method to collect paths
        if i == 0 or j == 0:
            return [current[::-1]]
        
        paths = []
        if self.s1[i-1] == self.s2[j-1]:
            current.append(self.s1[i-1])
            paths.extend(self._all_paths(i-1, j-1, current))
            current.pop()
        else:
            if self.dp[i-1][j] == self.dp[i][j]:
                paths.extend(self._all_paths(i-1, j, current))
            if self.dp[i][j-1] == self.dp[i][j]:
                paths.extend(self._all_paths(i, j-1, current))
        return paths
    
    def get_all_lcs(self):
        # Public method to get final results
        lcs_list = self._all_paths(len(self.s1), len(self.s2), [])
        unique_lcs = list(set(lcs_list))
        lcs_length = len(unique_lcs[0]) if unique_lcs else 0
        return lcs_length, unique_lcs

Usage is clean and self-contained:

processor = LCSProcessor("abcde", "ace")
length, sequences = processor.get_all_lcs()
print(f"Longest LCS length: {length}")
print(f"All LCS sequences: {sequences}")

This is the best approach if you’re building a larger system with multiple LCS-related operations—each instance manages its own state, and there’s no risk of cross-contamination between different LCS computations.

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