public int minDistance(String word1, String word2) {
        int[][] memo = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0; i < word1.length() + 1; i++){
            memo[i][0] = i;
        }

        for(int j = 0; j < word2.length() + 1; j++){
            memo[0][j] = j;
        }

        for(int i = 1; i < word1.length() + 1; i++){
            for(int j = 1; j < word2.length() + 1; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    memo[i][j] = memo[i - 1][j - 1];
                }else{
                    memo[i][j] = Math.min(Math.min(memo[i - 1][j], memo[i][j - 1]), memo[i - 1][j - 1]) + 1;
                }
            }
        }
        return memo[word1.length()][word2.length()];
    }