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 
3 private Levenshtein() {
4 }
5 
6 public static int distance(CharSequence a, CharSequence b) {
7 if (a.equals(b)) {
8 return 0;
9 }
10 if (a.length() == 0) {
11 return b.length();
12 }
13 if (b.length() == 0) {
14 return a.length();
15 }
16 
17 int[] previous = new int[b.length() + 1];
18 int[] current = new int[b.length() + 1];
19 
20 for (int j = 0; j <= b.length(); j++) {
21 previous[j] = j;
22 }
23 
24 for (int i = 1; i <= a.length(); i++) {
25 current[0] = i;
26 char ca = a.charAt(i - 1);
27 
28 for (int j = 1; j <= b.length(); j++) {
29 int cost = ca == b.charAt(j - 1) ? 0 : 1;
30 current[j] = Math.min(
31 Math.min(current[j - 1] + 1, previous[j] + 1),
32 previous[j - 1] + cost);
33 }
34 
35 int[] swap = previous;
36 previous = current;
37 current = swap;
38 }
39 
40 return previous[b.length()];
41 }
42 
43 public static double similarity(CharSequence a, CharSequence b) {
44 int maxLen = Math.max(a.length(), b.length());
45 if (maxLen == 0) {
46 return 1.0;
47 }
48 return 1.0 - (double) distance(a, b) / maxLen;
49 }
50 
51 public static boolean matches(CharSequence a, CharSequence b, int maxEdits) {
52 return distance(a, b) <= maxEdits;
53 }
54}
01 / 01
STEP 01

Walkthrough

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

Related explainers

java 
@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {
 

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter
Advanced 10 steps
java 
package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern
Intermediate 5 steps
java 
public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding
Intermediate 6 steps
java 
public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io
Intermediate 8 steps
java 
public final class EncodingDetector {
 
    public enum Encoding {
        UTF_8, UTF_16LE, UTF_16BE, UTF_32LE, UTF_32BE, ASCII, UNKNOWN

Detecting text encoding from raw bytes in Java

byte-manipulation encoding-detection bitwise-operations
Intermediate 8 steps
java 
public final class ImportOrganizer {
 
    private static final Pattern IMPORT_LINE =
            Pattern.compile("^import\\s+(static\\s+)?([\\w.]+(?:\\.\\*)?)\\s*;\\s*$");

Sorting Java imports with a regex pass

regex sorting text-processing
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Two-row Levenshtein distance in Java — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code