longest common subsequence in csharp

main.cs
public static int LongestCommonSubsequence(string s1, string s2)
{
    int m = s1.Length;
    int n = s2.Length;

    // Initialize the array to store the solutions to subproblems
    int[,] dp = new int[m + 1, n + 1];

    // Fill the array in a bottom-up manner
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1] + 1;
            }
            else
            {
                dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
    }

    // The length of the longest common subsequence is stored in the last cell of the array
    return dp[m, n];
}
706 chars
28 lines

main.cs
public static string LongestCommonSubsequenceString(string s1, string s2)
{
    int m = s1.Length;
    int n = s2.Length;

    // Initialize the array to store the solutions to subproblems
    int[,] dp = new int[m + 1, n + 1];

    // Initialize the array to store the directions of the optimal subproblems
    char[,] directions = new char[m + 1, n + 1];

    // Fill the arrays in a bottom-up manner
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1] + 1;
                directions[i, j] = '\\'; // Backslash indicates a diagonal arrow
            }
            else
            {
                if(dp[i - 1, j] >= dp[i, j - 1])
                {
                    dp[i, j] = dp[i - 1, j];
                    directions[i, j] = '|'; // Pipe indicates a vertical arrow
                }
                else
                {
                    dp[i, j] = dp[i, j - 1];
                    directions[i, j] = '-'; // Dash indicates a horizontal arrow
                }
            }
        }
    }

    // Reconstruct the longest common subsequence from the directions array
    StringBuilder sb = new StringBuilder();
    int x = m;
    int y = n;
    while(x > 0 && y > 0)
    {
        if(directions[x, y] == '\\')
        {
            sb.Insert(0, s1[x - 1]);
            x--;
            y--;
        }
        else if(directions[x, y] == '|')
        {
            x--;
        }
        else
        {
            y--;
        }
    }

    // The reconstructed subsequence is the longest common subsequence
    return sb.ToString();
}
1682 chars
63 lines