You are viewing a single comment's thread. Return to all comments →
C# solution:
public static string FindLcs (int[] a, int[] b) { var cache = new int[b.Length + 1, a.Length + 1]; InitCache(cache); FillDpTable(cache, a, b); return ConstructLcsString(a, cache); } private static void InitCache(int[,] cache) { for (int i = 0; i < cache.GetLength(0); i++) { cache[i, 0] = 0; } for (int i = 0; i < cache.GetLength(1); i++) { cache[0, i] = 0; } } private static void FillDpTable(int[,] cache, int[] row, int[] col) { for (int i = 1; i <= col.Length; i++) { for (int j = 1; j <= row.Length; j++) { if (col[i - 1] == row[j - 1]) { cache[i, j] = 1 + cache[i - 1, j - 1]; } else { cache[i, j] = Math.Max(cache[i - 1, j], cache[i, j - 1]); } } } } private static string ConstructLcsString(int[] row, int[,] cache) { string result = ""; int i = cache.GetLength(0) - 1; int j = cache.GetLength(1) - 1; while (i > 0 && j > 0) { if (cache[i, j - 1] != cache[i, j] && cache[i - 1, j] != cache[i, j]) { result = row[j - 1] + " " + result; i--; j--; } else if (cache[i - 1, j] == cache[i, j]) { i--; } else { j--; } } return result.Trim(); }
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence (LCS)
You are viewing a single comment's thread. Return to all comments →
C# solution: