The Second Most Popular Dynamic Programming Problem

-
How many Edit Distance problems are there? I guess a very high number.. This is the second most popular Dynamic Programming problem out there (guess the #1? Yeah, Fibonacci. By a mile).

Here is another version of the Edit Distance problem: https://leetcode.com/problems/one-edit-distance/

161. One Edit Distance
Medium
Given two strings s and t, determine if they are both one edit distance apart.
Note: 
There are 3 possiblities to satisify one edit distance apart:
  1. Insert a character into s to get t
  2. Delete a character from s to get t
  3. Replace a character of s to get t
Example 1:
Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.
Accepted
96,242
Submissions
299,225

This is 100% Edit Distance: build the DP table, and at the very end, just make sure that the last cell in your DP table is equal to... to... yes, 1 (one). Code is below, cheers, ACC.


public class Solution
{
    public bool IsOneEditDistance(string s, string t)
    {
        if (String.IsNullOrEmpty(s) && String.IsNullOrEmpty(t)) return false;
        if (String.IsNullOrEmpty(s)) return t.Length == 1;
        if (String.IsNullOrEmpty(t)) return s.Length == 1;

         int[][] dp = new int[s.Length + 1][];
        for (int i = 0; i < dp.Length; i++) dp[i] = new int[t.Length + 1];

         dp[0][0] = 0;
        for (int i = 1; i < dp.Length; i++) dp[i][0] = i;
        for (int j = 1; j < dp[0].Length; j++) dp[0][j] = j;

         for (int i = 1; i < dp.Length; i++)
        {
            for (int j = 1; j < dp[0].Length; j++)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] = Math.Min(Math.Min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }

         return dp[dp.Length - 1][dp[0].Length - 1] == 1;
    }
}

Comments

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more