C# longest subsequence solution


  • 0
    B

    I would recommend checking out this video for help: https://www.youtube.com/watch?v=HgUOWB0StNE

    After watching this and trying it on paper, I was able come up with a solution.

    public class Solution {
        public int MinDistance(string word1, string word2) {
            int[,] dp = new int[word1.Length+1, word2.Length+1];
            
            for(int i = 0; i <= word1.Length; i++) {
                for(int j = 0; j <= word2.Length; j++) {
                    if(i == 0 || j == 0) {
                        dp[i,j] = 0;
                    }
                    else if(word1[i-1] == word2[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]);
                    }
                }
            }
            
            return (word1.Length + word2.Length) - (dp[word1.Length, word2.Length] * 2);
        }
    }
    

Log in to reply
 

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