Longest common subsequence (LCS) brute force algorithm

Question

I want to create a brute force algorithm to find the largest common subsequence between 2 strings, but I'm struggling to enumerate all possibilities in the form of a algorithm.

I don't want a dynamic programming answer as oddly enough I manage to figure this one out (You would think the brute force method would be easier). Please use pseudo code, as I prefer to understand it and write it up myself.

Answer 1

It's pretty much the same as DP minus the memoization part.

LCS(s1, s2, i, j):
    if(i == -1 || j == -1)
        return 0
    if(s1[i] == s2[j])
        return 1 + LCS(s1, s2, i-1, j-1)
    return max(LCS(s1, s2, i-1, j), LCS(s1, s2, i, j-1))

The idea is if we have two strings s1 and s2 where s1 ends at i and s2 ends at j, then the LCS is:

• if either string is empty, then the longest common subsequence is 0.
• If the last character (index i) of string 1 is the same as the last one in string 2 (index j), then the answer is 1 plus the LCS of s1 and s2 ending at i-1 and j-1, respectively. Because it's obvious that those two indices contribute to the LCS, so it's optimal to count them.
• If the last characters don't match, then we try to remove one of the characters. So we try finding LCS between s1 (ending at i-1) and s2 (ending at j) and the LCS between s1 (ending at i) and s2 (ending at j-1), then take the max of both.

The time complexity is obviously exponential.