Dynamic Programming with Strings

-
In this post, I'm going to discuss the "Edit Distance" problem, along with a specific case of it - the "Longest Common Subsequence" problem. 

Edit Distance

The problem: Given two strings "a" and "b" - find the smallest number of edits we need to transform "a" into "b." The possible types of edits are "insertion," "deletion," and "replacement." Assume all the edits have the same cost of 1. 

The approach: We can break this problem down into prefix or suffix subproblems. (It doesn't matter which one we pick - the approaches are equivalent.) If we think in terms of prefixes, we can call E(i, j) the minimum cost of transforming the first i characters of "a" into the first j characters of "b." There are four ways we can reduce E(i, j) into smaller subproblems... 

1) If the ith character of "a" and the jth character of "b" are already equal, then we don't have to do anything! Then, E(i, j) is reduced to E(i-1, j-1) without any cost. 

2) We can delete the ith character of "a" and transform the first i-1 characters of "a" into the first j characters of "b." Then, E(i, j) is reduced to 1 + E(i-1, j). 

3) We can transform the first i characters of "a" into the first j-1 characters of "b" and insert the jth character of "b." Then, E(i, j) is reduced to E(i, j-1) + 1. 

4) Finally, we can transform the first i-1 characters of "a" into the first j-1 characters of "b" and replace the ith character of "a" with the jth character of "b." Then, E(i, j) is reduced to E(i-1, j-1) + 1.


This approach is O(mn), where m and n are the respective lengths of the two strings. Written in code, this solution looks like... 

static int[][] tab; 

public static int minEditDistance(String a, String b) {
for(int i = 0; i <= a.length(); i++) {
for(int j = 0; j <= b.length(); j++) {
if(i == 0) tab[i][j] = j; //delete all j characters of b
else if(j == 0) tab[i][j] = i; //delete all i characters of a
else if(a.charAt(i-1) == b.charAt(j-1)) tab[i][j] = tab[i-1][j-1];
else tab[i][j] = 1 + Math.min(Math.min(tab[i-1][j], tab[i][j-1]), tab[i-1][j-1]); 
}
}
return tab[a.length()][b.length()]; 
}

Longest Common Subsequence 

The LCS problem is a special case of the Edit Distance problem where the insertion cost and deletion cost are 1, and the replacement cost is 0 if the two characters are equal and infinity if the two characters are different. 

The problem: Given two strings "a" and "b", find the length of their longest common sequence. 

The approach: Call L(i, j) the length of the LCS of the first i characters in "a" and the first j characters in "b." There are two cases:

1) If the ith character of "a" and the jth character of "b" are equal, then L(i, j) is reduced to 1 + L(i-1, j-1).

2) If they are different, then L(i,j) is reduced to the maximum of L(i-1, j) and L(i, j-1). 

My code for this approach is below. Note that if i or j is 0, then the LCS is 0 (there are no common characters because there are no characters in the first place.) 

public static int lcs(String a, String b) {
for(int i = 1; i <= a.length(); i++) {
for(int j = 1; j <= b.length(); j++) {
if(a.charAt(i-1) == b.charAt(j-1)) {
tab[i][j] = 1 + tab[i-1][j-1];
}
else tab[i][j] = Math.max(tab[i][j-1], tab[i-1][j]);
}
}
return tab[a.length()][b.length()]; 
} 

All code on my Github - try running it yourself!

Source(s): MIT OCW, Clemson

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each instance of a type that impleme
Read more

Building A Toy Language Interpreter in Go

-
Image
In this post, I'll be giving a high-level overview of interpreters, why they're interesting, and how they work. I'll be referencing my repo, go_interpreter , which is a simple interpreter written in Go for a toy language. The figure below shows the structure of our interpreter with an example input: What is an interpreter?  An interpreter is a language processor that seems to directly execute the source program on user input: In contrast, a compiler first takes in a source program and translates it to an executable machine code target program. Then, the user can pass in inputs to this target program and get outputs. In general, an interpreter is better at reporting errors since it's processing statements one at a time, and a compiler is faster at generating outputs from inputs. In this post, we're going to go over a simple interpreter that is capable of supporting: integers, booleans, strings, arrays, hashmaps prefix, infix operators index opera
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized
Read more