String transformations are an essential concept in computer science, helping us solve problems in text processing, spell-checking, and more.
One classic problem in this domain is the Edit Distance, also known as the Levenshtein distance.
Given two strings, word1 and word2, both consisting of lowercase English letters, your task is to determine the minimum number of operations required to convert word1 into word2.
The goal is to minimize the total number of these operations.
This problem challenges you to identify overlapping subproblems and use efficient techniques like dynamic programming to solve them. It highlights how subtle variations in character sequences can lead to vastly different outcomes.
Whether you’re preparing for coding interviews or honing your algorithmic skills, tackling the distinct subsequences problem is a great way to deepen your understanding of string manipulation.
Explanation:
"s" to get "monkey"."k" to get "money".Explanation:
Constraints
The lengths of word1 and word2 are between 0 and 100.
Both strings consist of lowercase English letters.
Edit distance has practical applications across domains:
This problem typically employs dynamic programming, where a matrix is used to store intermediate results for the smallest edit distances of substrings. The key lies in solving smaller subproblems and building up to the full solution efficiently.
Mastering this problem not only sharpens your algorithmic skills but also gives you insight into real-world applications of string manipulation techniques.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
def dfs(i, j):
if i == m:
return n - j
if j == n:
return m - i
if word1[i] == word2[j]:
return dfs(i + 1, j + 1)
res = min(dfs(i + 1, j), dfs(i, j + 1))
res = min(res, dfs(i + 1, j + 1))
return res + 1
return dfs(0, 0)class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
return dfs(0, 0, word1, word2, m, n);
}
int dfs(int i, int j, string& word1, string& word2, int m, int n) {
if (i == m) return n - j;
if (j == n) return m - i;
if (word1[i] == word2[j]){
return dfs(i + 1, j + 1, word1, word2, m, n);
}
int res = min(dfs(i + 1, j, word1, word2, m, n),
dfs(i, j + 1, word1, word2, m, n));
res = min(res, dfs(i + 1, j + 1, word1, word2, m, n));
return res + 1;
}
};public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
return dfs(0, 0, word1, word2, m, n);
}
private int dfs(int i, int j, String word1, String word2, int m, int n) {
if (i == m) return n - j;
if (j == n) return m - i;
if (word1.charAt(i) == word2.charAt(j)) {
return dfs(i + 1, j + 1, word1, word2, m, n);
}
int res = Math.min(dfs(i + 1, j, word1, word2, m, n),
dfs(i, j + 1, word1, word2, m, n));
res = Math.min(res, dfs(i + 1, j + 1, word1, word2, m, n));
return res + 1;
}
}class Solution {
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dfs = (i, j) => {
if (i === m) return n - j;
if (j === n) return m - i;
if (word1[i] === word2[j]) {
return dfs(i + 1, j + 1);
}
let res = Math.min(dfs(i + 1, j), dfs(i, j + 1));
res = Math.min(res, dfs(i + 1, j + 1));
return res + 1;
};
return dfs(0, 0);
}
}class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = {}
def dfs(i, j):
if i == m:
return n - j
if j == n:
return m - i
if (i, j) in dp:
return dp[(i, j)]
if word1[i] == word2[j]:
dp[(i, j)] = dfs(i + 1, j + 1)
else:
res = min(dfs(i + 1, j), dfs(i, j + 1))
res = min(res, dfs(i + 1, j + 1))
dp[(i, j)] = res + 1
return dp[(i, j)]
return dfs(0, 0)public class Solution {
private int[][] dp;
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return dfs(0, 0, word1, word2, m, n);
}
private int dfs(int i, int j, String word1, String word2, int m, int n) {
if (i == m) return n - j;
if (j == n) return m - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = dfs(i + 1, j + 1, word1, word2, m, n);
} else {
int res = Math.min(dfs(i + 1, j, word1, word2, m, n),
dfs(i, j + 1, word1, word2, m, n));
res = Math.min(res, dfs(i + 1, j + 1, word1, word2, m, n));
dp[i][j] = res + 1;
}
return dp[i][j];
}
}
class Solution {
vector> dp;
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
dp = vector>(m, vector(n, -1));
return dfs(0, 0, word1, word2, m, n);
}
int dfs(int i, int j, string& word1, string& word2, int m, int n) {
if (i == m) return n - j;
if (j == n) return m - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1[i] == word2[j]){
dp[i][j] = dfs(i + 1, j + 1, word1, word2, m, n);
} else {
int res = min(dfs(i + 1, j, word1, word2, m, n),
dfs(i, j + 1, word1, word2, m, n));
res = min(res, dfs(i + 1, j + 1, word1, word2, m, n));
dp[i][j] = res + 1;
}
return dp[i][j];
}
}; class Solution {
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
minDistance(word1, word2) {
const m = word1.length, n = word2.length;
let dp = Array.from({ length: m + 1 }, () =>
Array(n + 1).fill(-1));
const dfs = (i, j) => {
if (i === m) return n - j;
if (j === n) return m - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1[i] === word2[j]) {
dp[i][j] = dfs(i + 1, j + 1);
} else {
let res = Math.min(dfs(i + 1, j), dfs(i, j + 1));
res = Math.min(res, dfs(i + 1, j + 1));
dp[i][j] = res + 1;
}
return dp[i][j];
};
return dfs(0, 0);
}
}class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]
for j in range(len(word2) + 1):
dp[len(word1)][j] = len(word2) - j
for i in range(len(word1) + 1):
dp[i][len(word2)] = len(word1) - i
for i in range(len(word1) - 1, -1, -1):
for j in range(len(word2) - 1, -1, -1):
if word1[i] == word2[j]:
dp[i][j] = dp[i + 1][j + 1]
else:
dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])
return dp[0][0]public class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int j = 0; j <= word2.length(); j++) {
dp[word1.length()][j] = word2.length() - j;
}
for (int i = 0; i <= word1.length(); i++) {
dp[i][word2.length()] = word1.length() - i;
}
for (int i = word1.length() - 1; i >= 0; i--) {
for (int j = word2.length() - 1; j >= 0; j--) {
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = dp[i + 1][j + 1];
} else {
dp[i][j] = 1 + Math.min(dp[i + 1][j],
Math.min(dp[i][j + 1], dp[i + 1][j + 1]));
}
}
}
return dp[0][0];
}
}public class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int j = 0; j <= word2.length(); j++) {
dp[word1.length()][j] = word2.length() - j;
}
for (int i = 0; i <= word1.length(); i++) {
dp[i][word2.length()] = word1.length() - i;
}
for (int i = word1.length() - 1; i >= 0; i--) {
for (int j = word2.length() - 1; j >= 0; j--) {
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = dp[i + 1][j + 1];
} else {
dp[i][j] = 1 + Math.min(dp[i + 1][j],
Math.min(dp[i][j + 1], dp[i + 1][j + 1]));
}
}
}
return dp[0][0];
}
}class Solution {
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
minDistance(word1, word2) {
const dp = new Array(word1.length + 1)
.fill(0)
.map(() => new Array(word2.length + 1).fill(0));
for (let j = 0; j <= word2.length; j++) {
dp[word1.length][j] = word2.length - j;
}
for (let i = 0; i <= word1.length; i++) {
dp[i][word2.length] = word1.length - i;
}
for (let i = word1.length - 1; i >= 0; i--) {
for (let j = word2.length - 1; j >= 0; j--) {
if (word1[i] === word2[j]) {
dp[i][j] = dp[i + 1][j + 1];
} else {
dp[i][j] =
1 +
Math.min(
dp[i + 1][j],
Math.min(dp[i][j + 1], dp[i + 1][j + 1]),
);
}
}
}
return dp[0][0];
}
}class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
if m < n:
m, n = n, m
word1, word2 = word2, word1
dp = [0] * (n + 1)
nextDp = [0] * (n + 1)
for j in range(n + 1):
dp[j] = n - j
for i in range(m - 1, -1, -1):
nextDp[n] = m - i
for j in range(n - 1, -1, -1):
if word1[i] == word2[j]:
nextDp[j] = dp[j + 1]
else:
nextDp[j] = 1 + min(dp[j], nextDp[j + 1], dp[j + 1])
dp = nextDp[:]
return dp[0]class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
if (m < n) {
int temp = m;
m = n;
n = temp;
String t = word1;
word1 = word2;
word2 = t;
}
int[] dp = new int[n + 1];
int[] nextDp = new int[n + 1];
for (int j = 0; j <= n; j++) {
dp[j] = n - j;
}
for (int i = m - 1; i >= 0; i--) {
nextDp[n] = m - i;
for (int j = n - 1; j >= 0; j--) {
if (word1.charAt(i) == word2.charAt(j)) {
nextDp[j] = dp[j + 1];
} else {
nextDp[j] = 1 + Math.min(dp[j],
Math.min(nextDp[j + 1], dp[j + 1]));
}
}
System.arraycopy(nextDp, 0, dp, 0, n + 1);
}
return dp[0];
}
}class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
if (m < n) {
swap(m, n);
swap(word1, word2);
}
vector dp(n + 1), nextDp(n + 1);
for (int j = 0; j <= n; ++j) {
dp[j] = n - j;
}
for (int i = m - 1; i >= 0; --i) {
nextDp[n] = m - i;
for (int j = n - 1; j >= 0; --j) {
if (word1[i] == word2[j]) {
nextDp[j] = dp[j + 1];
} else {
nextDp[j] = 1 + min({dp[j], nextDp[j + 1], dp[j + 1]});
}
}
dp = nextDp;
}
return dp[0];
}
}; class Solution {
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
minDistance(word1, word2) {
let m = word1.length, n = word2.length;
if (m < n) {
[m, n] = [n, m];
[word1, word2] = [word2, word1];
}
let dp = new Array(n + 1).fill(0);
let nextDp = new Array(n + 1).fill(0);
for (let j = 0; j <= n; j++) {
dp[j] = n - j;
}
for (let i = m - 1; i >= 0; i--) {
nextDp[n] = m - i;
for (let j = n - 1; j >= 0; j--) {
if (word1[i] === word2[j]) {
nextDp[j] = dp[j + 1];
} else {
nextDp[j] = 1 + Math.min(dp[j],
Math.min(nextDp[j + 1], dp[j + 1]));
}
}
dp = [...nextDp];
}
return dp[0];
}
}
Get Hiring Updates right in your inbox from PrepInsta