Welcome to WuJiGu Developer Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
384 views
in Technique[技术] by (71.8m points)

c++ - Does it matter which string is taken along the row and column in Min Edit Distance Problem?

The Problem:-
enter image description here

So, i have taken the second string along the row and the first string along the columns-I am getting the wrong answer because of this. But i dont understand how and why??
also, for some value(i.e "table" and "bal") i am getting segmentation fault.


#include <vector>
#include <string>
#include <iostream>
using namespace std;

void print(vector<vector<int>> &table)
{
    for(int i = 0; i < table.size(); ++i)
    {
        for(int j = 0; j < table[0].size(); ++j)
            cout << table[i][j] << " ";
        cout << endl;
    }
}
int levenshteinDistance(string a, string b) 
{
    int r = b.size() + 1;
    int c = a.size() + 1;
    vector<vector<int>> table(r, vector<int>(c, 0));
    for(int i = 0; i < r; ++i)
        table[i][0] = i;
    for(int j = 0; j < c; ++j)
        table[0][j] = j;
    
    for(int i = 1; i < r; ++i)
    {
        for(int j = 1; j < c; ++j)
        {
            
            if(a[j - 1] != b[i - 1])
            {
                table[i][j] = 1 + min(table[i - 1][j - 1], 
                                                min(table[j - 1][i], table[i - 1][j]));
            }
            else
                table[i][j] = table[i - 1][j - 1];
            
        }
        
    }

    print(table);
  return table[r-1][c-1];
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神答复

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to WuJiGu Developer Q&A Community for programmer and developer-Open, Learning and Share
...