10+ Lines Simple C# Code ~100ms


  • 0
        public int MinDistance(string s1, string s2) {
            int[,] lcsTable = new int[s1.Length + 1, s2.Length + 1];
                int lcsLength = 0;
                string lcsString = string.Empty;
                int row = 0, column = 0;
                for (row = 1; row < s1.Length + 1; row++)           
                    for (column = 1; column < s2.Length + 1; column++)
                       if (s1[row - 1] == s2[column - 1])
                            lcsTable[row, column] = lcsTable[row - 1, column - 1] + 1;
                        else
                            lcsTable[row, column] = Math.Max(lcsTable[row - 1, column], lcsTable[row, column - 1]);          
             lcsLength = lcsTable[s1.Length, s2.Length];
             return (s1.Length - lcsLength) + (s2.Length - lcsLength);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.