英文:
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.
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 = "sea", word2 = "eat"
Output: 2
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< 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 ;
}
`
答案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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论