关于暴力求解最长公共子序列（LCS）算法的正确性及实现问询

First off, let's get straight to the point: your code isn't a valid Longest Common Subsequence (LCS) implementation, and it's not even a brute-force approach—it uses a greedy strategy that will miss the actual longest subsequence in many cases.

Why Your Code Fails #

Here's what your code does: it starts at each position in s1, then tries to match subsequent characters in order in s2 (once it finds a match, it moves the s2 pointer forward and never looks back). This only finds subsequences that start at a given s1 index and follow a strict left-to-right path in s2—it doesn't enumerate all possible subsequence combinations, so it can easily overlook longer valid LCS entries.

Take this test case for example:

• s1 = "abcfbc"
• s2 = "abfcab"

The actual LCS here is "abfb" or "abcb" (length 4), but your code will return something like "ab" or "cb" (length 2)—completely missing the longest valid result.

What a Real Brute-Force LCS Algorithm Looks Like #

A true brute-force approach works by generating every possible subsequence of s1, checking if that subsequence exists in s2, and keeping track of the longest one that does.

Since a string of length n has 2^n subsequences, this approach has a time complexity of O(2^n * m) (where n is the length of the shorter string, m the longer one). It's extremely inefficient—great for learning, but useless for real-world use cases.

Correct Brute-Force Implementation (Java) #

Here's a brute-force solution that returns the actual LCS string, using recursion and backtracking to enumerate all subsequences:

public class LCSBruteForce {
    private String longestLcs = "";

    public String lcs(String s1, String s2) {
        longestLcs = "";
        generateAllSubsequences(s1, 0, new StringBuilder(), s2);
        return longestLcs;
    }

    private void generateAllSubsequences(String source, int currentIndex, StringBuilder currentSubseq, String target) {
        // Check if current subsequence is valid and longer than our current best
        if (isValidSubsequence(currentSubseq.toString(), target) && currentSubseq.length() > longestLcs.length()) {
            longestLcs = currentSubseq.toString();
        }

        // Recursively build all possible subsequences
        for (int i = currentIndex; i < source.length(); i++) {
            currentSubseq.append(source.charAt(i));
            generateAllSubsequences(source, i + 1, currentSubseq, target);
            currentSubseq.deleteCharAt(currentSubseq.length() - 1); // Backtrack to try next combination
        }
    }

    // Helper to check if a string is a subsequence of the target
    private boolean isValidSubsequence(String candidate, String target) {
        int candidatePtr = 0;
        for (char c : target.toCharArray()) {
            if (candidatePtr < candidate.length() && c == candidate.charAt(candidatePtr)) {
                candidatePtr++;
            }
        }
        return candidatePtr == candidate.length();
    }
}

How This Works: #

• Generate All Subsequences: The generateAllSubsequences method uses recursion and backtracking to create every possible subsequence of s1—every choice to include or exclude a character is explored.
• Validate Subsequences: The isValidSubsequence method checks if the current subsequence exists in s2 by scanning s2 and matching characters in order.
• Track the Longest: Every time we generate a valid subsequence that's longer than our current best, we update our result.

A Quick Note #

Brute-force LCS is never practical for real use—even strings of length 20 will take an unreasonable amount of time to process. For actual applications, use the dynamic programming approach which runs in O(n*m) time, far more efficient than brute-force.

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