Halvor Strand

	public static int levenshteinDistance(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		for(int i = 0; i <= a.length(); i++)
			c[i][0] = i;

		for(int j = 0; j <= b.length(); j++)
			c[0][j] = j;

		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))
                    	c[i][j] = c[i-1][j-1];
                    else
                    	c[i][j] = Math.min(c[i-1][j] + 1, Math.min(c[i][j-1] + 1, c[i-1][j-1] + 1));

		return c[a.length()][b.length()];
	}

Code

XKCD

Geeking

	// time: Ο(length(a)*length(b))
	// space: Θ(length(a)*length(b))
	public static int lcs(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		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))
                    	c[i][j] = c[i-1][j-1] + 1;
                    else
                    	c[i][j] = Math.max(c[i-1][j], c[i][j-1]);

		return c[a.length()][b.length()];
	}

Code