edit_distance_1639.cpp (670B)
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 6 int d(const std::string& a, const std::string& b, size_t i, size_t j, 7 std::vector<std::vector<int>>& t) { 8 if (t[i][j] != -1) return t[i][j]; 9 if (i == a.size()) return t[i][j] = b.size()-j; 10 if (j == b.size()) return t[i][j] = a.size()-i; 11 if (a[i] == b[j]) return t[i][j] = d(a, b, i+1, j+1, t); 12 return t[i][j] = 1+std::min(d(a, b, i+1, j+1, t), 13 std::min(d(a, b, i+1, j, t), d(a, b, i, j+1, t))); 14 } 15 16 int main() { 17 std::string a, b; 18 std::cin >> a >> b; 19 std::vector<std::vector<int>> 20 t(a.size()+1, std::vector<int>(b.size()+1, -1)); 21 std::cout << d(a, b, 0, 0, t) << "\n"; 22 }