Minimum Edit Distance-Dynamic Programming


  • 0
    S
    class Solution {
        public int minDistance(String word1, String word2) 
        {
             int[][] editDistMatrix=new int[word1.length()+1][word2.length()+1];
             for(int i=0;i<word1.length()+1;i++)
             {
            	 editDistMatrix[i][0]=i;
             }
             for(int j=0;j<word2.length()+1;j++)
             {
            	 editDistMatrix[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))
                         {
                        	 editDistMatrix[i][j]=editDistMatrix[i-1][j-1];
                        	 
                         }
                         else
                         {
                        	 editDistMatrix[i][j]=1+Math.min(editDistMatrix[i-1][j]
                                                          ,Math.min( editDistMatrix[i][j-1],
                                                          editDistMatrix[i-1][j-1]));
                         }
                     
                 }
             }
             return editDistMatrix[word1.length()][word2.length()];
        }
        
    }
    

Log in to reply
 

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