Levenshtein Distance Time : O(nm) Space : O(min(n,m)) 123456789101112131415161718192021222324using namespace std;int levenshteinDistance(string str1, string str2) { if(str1.length() < str2.length()) return levenshteinDistance(str2, str1); int n = str1.length(), m = str2.length(); vector<int> dp(m + 1, 0); for(int i = 0; i <= m; i++) dp[i] = i; for(int i = 1; i <= n; i++) { vector<int> ndp(m + 1, i); for(int j = 1; j <= m; j++) { if(str1[i-1] == str2[j-1]) { ndp[j] = dp[j-1]; } else { ndp[j] = 1 + min({ndp[j-1], dp[j-1], dp[j]}); } } swap(dp, ndp); } return dp.back();}