█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5502

Problema 0x91 - Distancia de Levenshtein

  • Autor: DanielP
  • Fecha: 2021-12-27 04:01:07 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.003 s 4 KBi
#2
Correcto
0.002 s 4 KBi
#3
Correcto
0.008 s 4 KBi
#4
Correcto
0.01 s 46 KBi
#5
Correcto
0.002 s 4 KBi
#6
Correcto
0.006 s 26 KBi
#7
Correcto
0.004 s 4 KBi
#8
Correcto
0.009 s 4 KBi
#9
Correcto
0.002 s 4 KBi
#10
Correcto
0.003 s 4 KBi
#11
Correcto
0.003 s 4 KBi
#12
Correcto
0.004 s 4 KBi
#13
Correcto
0.003 s 4 KBi
#14
Correcto
0.012 s 71 KBi
#15
Correcto
0.009 s 6 KBi
#16
Correcto
0.007 s 4 KBi
#17
Correcto
0.007 s 4 KBi
#18
Correcto
0.009 s 4 KBi
#19
Correcto
0.003 s 4 KBi
#20
Correcto
0.007 s 4 KBi
#21
Correcto
0.044 s 14 KBi
#22
Correcto
0.053 s 4 KBi
#23
Correcto
0.044 s 28 KBi
#24
Correcto
0.021 s 4 KBi
#25
Correcto
0.029 s 4 KBi
#26
Correcto
0.051 s 4 KBi
#27
Correcto
0.049 s 4 KBi
Puntos totales: 100 / 100

Código

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(), s.end()
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
char el = '\n';
char esp = ' ';

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ostream& operator<<(ostream& os, const vector<int> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

string a,b;

const int N = 1005;

int dp[N][N];

const int oo = 1e9+7;

int n,m;

int go(int i, int j){
    if(i == n && j == m) return 0;
    if(i >=n || j >= m) return oo;
    int &ans = dp[i][j];
    if(ans == -1){
        ans = oo;
        ckmin(ans,go(i + 1,j) + 1);  //
        ckmin(ans,go(i,j + 1) + 1);
        ckmin(ans,go(i + 1,j + 1) + (a[i] != b[j]));
    }
    return ans;
}


int main(){
	fast_io;
	/*
 	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    cin>>a>>b;
    a.pb('.'), b.pb('.');
    n = a.size();
    m = b.size();
    memset(dp,-1,sizeof dp);
    cout<<go(0,0)<<el;
}

/*

*/