删除两个字符串的操作:记忆数组值的含义

huangapple go评论72阅读模式
英文:

Delete Operation for Two Strings : memoisation array value meaning

问题

以下是您要翻译的代码部分:

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++)
    {
        for( int j =0 ; j< word2.length() + 1 ;j++)
        {
           memo[i][j]=-1; 
        }
    }
    int ans = solver(word1,word2,0,0,memo) ;
    printMemo(memo);
    return ans;
}

public int solver(String word1, String word2,int i ,int j,int[][] memo) {
     if( memo[i][j]!=-1)
        return memo[i][j];
      if( i==word1.length() && j==word2.length() )
      {
          return 0;
      }
      if( i==word1.length()  && j !=word2.length() )
      {
          return word2.length() -j;
      }
      if( j==word2.length()  && i !=word1.length() )
      {
          return word1.length()-i;
      }
      int del1=0;
      int del2=0;
      if( word1.charAt(i)==word2.charAt(j))
      {
          return  memo[i][j]=solver(word1,word2,i+1,j+1,memo);
      } else
      {
          del1= 1+solver(word1,word2,i+1,j,memo);
          del2= 1+ solver(word1,word2,i,j+1,memo);
      }
      int ans=Math.min(del1,del2);
      memo[i][j]= ans;
      return ans ;
}

希望这有助于您理解代码。如果您有任何其他问题,请随时提出。

英文:

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Leetcode question

I am able to write coorrect code and memoise it.But i have a doubt.
When i print the memo[][] array ,i get the below value for input
Input: word1 = &quot;sea&quot;, word2 = &quot;eat&quot;
Output: 2

Memo Array Pic

What i understand memo[i][j] number of min steps to make both words same ( 0,0 is Empty string )
so value of memo[0][0] should be 0 since it represent empty strings.
So why memo[0][0] ==2 and not 0?

public int minDistance(String word1, String word2) {
int[][] memo=new int[word1.length() + 1 ][word2.length() + 1 ];
for( int i =0 ; i&lt; word1.length() + 1  ;i++)
{
for( int j =0 ; j&lt; word2.length() + 1 ;j++)
{
memo[i][j]=-1; 
}
}
int ans = solver(word1,word2,0,0,memo) ;
printMemo(memo);
return ans;
}
public int solver(String word1, String word2,int i ,int j,int[][] memo) {
if( memo[i][j]!=-1)
return memo[i][j];
if( i==word1.length() &amp;&amp; j==word2.length() )
{
return 0;
}
if( i==word1.length()  &amp;&amp; j !=word2.length() )
{
return word2.length() -j;
}
if( j==word2.length()  &amp;&amp; i !=word1.length() )
{
return word1.length()-i;
}
int del1=0;
int del2=0;
if( word1.charAt(i)==word2.charAt(j))
{
return  memo[i][j]=solver(word1,word2,i+1,j+1,memo);
} else
{
del1= 1+solver(word1,word2,i+1,j,memo);
del2= 1+ solver(word1,word2,i,j+1,memo);
}
int ans=Math.min(del1,del2);
memo[i][j]= ans;
return ans ;
}

`

答案1

得分: 0

在这个特定的解决方案中,memo[i][j] 表示 word1[i..end]word2[j..end] 的成本。所以,基本情况memo[len1][len2] = 0,而 答案memo[0][0] 处。也许你对解决方案的 理解 暗示着要反过来做,但使用这段代码,就是这样。

英文:

In this particular solution, memo[i][j] means the cost for word1[i..end] and word2[j..end]. So, the base case is memo[len1][len2] = 0, and the answer is at memo[0][0]. Perhaps your understanding of the solution suggested to make it the other way around, but with this code, this is it.

huangapple
  • 本文由 发表于 2023年6月8日 01:24:45
  • 转载请务必保留本文链接:https://go.coder-hub.com/76425731.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定