| 370 | } |
| 371 | |
| 372 | uint64_t damerauLevenshteinDistance(const std::string& s1, const std::string& s2) { |
| 373 | const uint64_t m = s1.size(), n = s2.size(); |
| 374 | std::vector<std::vector<uint64_t>> dp(m + 1, std::vector<uint64_t>(n + 1, 0)); |
| 375 | for (uint64_t i = 0; i <= m; i++) { |
| 376 | dp[i][0] = i; |
| 377 | } |
| 378 | for (uint64_t j = 0; j <= n; j++) { |
| 379 | dp[0][j] = j; |
| 380 | } |
| 381 | for (uint64_t i = 1; i <= m; i++) { |
| 382 | for (uint64_t j = 1; j <= n; j++) { |
| 383 | if (s1[i - 1] == s2[j - 1]) { |
| 384 | dp[i][j] = dp[i - 1][j - 1]; |
| 385 | if (i > 1 && j > 1 && s1[i - 1] == s2[j - 2] && s1[i - 2] == s2[j - 1]) { |
| 386 | dp[i][j] = std::min(dp[i][j], dp[i - 2][j - 2]); |
| 387 | } |
| 388 | } else { |
| 389 | dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); |
| 390 | if (i > 1 && j > 1 && s1[i - 1] == s2[j - 2] && s1[i - 2] == s2[j - 1]) { |
| 391 | dp[i][j] = std::min(dp[i][j], dp[i - 2][j - 2] + 1); |
| 392 | } |
| 393 | } |
| 394 | } |
| 395 | } |
| 396 | return dp[m][n]; |
| 397 | } |
| 398 | |
| 399 | std::string findClosestCommand(std::string lineStr) { |
| 400 | std::string closestCommand = ""; |
no test coverage detected