java 54 lines · 8 steps

Two-row Levenshtein distance in Java

Compute edit distance between two strings using two rolling rows instead of a full matrix.

Explained by highlit

Intermediate dynamic-programming edit-distance space-optimization strings

1public final class Levenshtein {
2 
  private Levenshtein() {
  }
5 
  public static int distance(CharSequence a, CharSequence b) {
      if (a.equals(b)) {
          return 0;
      }
      if (a.length() == 0) {
          return b.length();
      }
      if (b.length() == 0) {
          return a.length();
      }
16 
      int[] previous = new int[b.length() + 1];
      int[] current = new int[b.length() + 1];
19 
      for (int j = 0; j <= b.length(); j++) {
          previous[j] = j;
      }
23 
      for (int i = 1; i <= a.length(); i++) {
          current[0] = i;
          char ca = a.charAt(i - 1);
27 
          for (int j = 1; j <= b.length(); j++) {
              int cost = ca == b.charAt(j - 1) ? 0 : 1;
              current[j] = Math.min(
                      Math.min(current[j - 1] + 1, previous[j] + 1),
                      previous[j - 1] + cost);
          }
34 
          int[] swap = previous;
          previous = current;
          current = swap;
      }
39 
      return previous[b.length()];
  }
42 
  public static double similarity(CharSequence a, CharSequence b) {
      int maxLen = Math.max(a.length(), b.length());
      if (maxLen == 0) {
          return 1.0;
      }
      return 1.0 - (double) distance(a, b) / maxLen;
  }
50 
  public static boolean matches(CharSequence a, CharSequence b, int maxEdits) {
      return distance(a, b) <= maxEdits;
  }
54}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Levenshtein distance counts the minimum single-character inserts, deletes, and substitutions to turn one string into another.
2The classic DP only ever reads the current and previous rows, so two arrays replace the full matrix and cut memory to O(n).
3Swapping row references each iteration reuses buffers without reallocating, keeping the inner loop allocation-free.

Related explainers

java

package com.example.lb;
 
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

A thread-safe round-robin load balancer in Java

concurrency load-balancing round-robin

Intermediate 9 steps

java

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion

Intermediate 8 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")