编程之美-计算字符串的相似度

public class StringDistance {

	/**
	 * 编程之美 计算字符串的相似度
	 * 我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
	 * 1.修改一个字符（如把“a”替换为“b”）;
	 * 2.增加一个字符（如把“abdd”变为“aebdd”）;
	 * 3.删除一个字符（如把“travelling”变为“traveling”）;
	 * 比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。
	 * 上面的两种方案，都仅需要一次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。
	 * 也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。
	 * 给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？
	 * 
	 * 解答：动态规划+备忘录
	 * 2012-11-04：主要思路还是递归。字符串记为A和B（当前比较的位置记为K，当前距离记为L），从第一个字符开始按位比较，分两种情况：
	 * 1、A和B在第K位的字符相等（L不变）。那好，各自向后移动，继续比较第K+1位
	 * 2、A和B在第K位的字符不相等（L=L+1）。采取递归，作三种操作，看哪种操作最后得到的距离最短：
	 * 一是A和B同时向后移动（相当于A和B同时删除这个字符），继续比较第K+1位
	 * 二是A移动B不移动，相当于A删除了这个字符，用剩余的字符与B作比较
	 * 三是A不移动B移动，相当于B删除了这个字符，用剩余的字符与A作比较
	 * 递归的好处就是可以递归得到这三种操作到最后得到的距离，哪个是最短
	 * 举个例子，A="abc",B="zbc"。我们可以一眼看出，采用第一种操作算得的距离最短（L=1）
	 * 但程序中要递归执行这另外两种操作并比较：
	 * A1="bc",B2="zbc" -->按位比较得到的L=1+3
	 * A2="abc",B2="bc" -->按位比较得到的L=1+3
	 * 因此程序会选择第一种操作，再接着进行第K+1位的比较
	 */
	
	private static int[][] record;	//记录子问题的解，0表示子问题未求解
	
	public static void main(String[] args) {
		String strA = "abcd";
		String[] strBB = {
				"",
				"z",
				"a",
				"ac",
				"adc"
		};
		for (String strB : strBB) {
			int distance = distanceBetween(strA, strB);
			System.out.println(distance);
		}
	}

	public static int distanceBetween(String strA, String strB) {
		int distance = -1;
		if (strA != null && strB != null) {
			int lenA = strA.length();
			int lenB = strB.length();
			if (lenA == 0 && lenB == 0) {
				distance = 0;
			}
			if (lenA != 0 && lenB == 0) {
				distance = lenA;
			}
			if (lenA == 0 && lenB != 0) {
				distance = lenB;
			}
			if (lenA != 0 && lenB != 0) {
				record = new int[lenA + 1][lenB + 1];
				char[] charArrayA = strA.toCharArray();
				char[] charArrayB = strB.toCharArray();
				distance = distanceHelp(charArrayA, charArrayB, 0, 0, lenA - 1, lenB - 1);
			}
		}
		return distance;
	}
	
	//endA和endB是不变的，因此记录子问题的解可用record[beginA][beginB]来表示
	public static int distanceHelp(char[] charArrayA, char[] charArrayB,
									 int beginA, int beginB, int endA, int endB) {
		if (beginA > endA) {				//递归出口：A从头到尾每个字符遍历完了，B有两种情况：
			if (beginB > endB) {			//1.B也同时遍历完了，说明这A=B
				return 0;	
			} else {
				return endB - beginB + 1;	//2.B还没遍历完，那B剩下的长度就是两个字符串不同的地方，即距离
			}
		}
		if (beginB > endB) {
			if (beginA > endA) {
				return 0;
			} else {
				return endA - beginA + 1;
			}
		}
		
		int distance = -1;
		if (charArrayA[beginA] == charArrayB[beginB]) {
			distance = record[beginA + 1][beginB + 1];
			if (distance == 0) {
				distance = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB);
			}
		} else {
			int d1 = record[beginA + 1][beginB];
			if (d1 == 0) {
				d1 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB, endA, endB); 
			}
			int d2 = record[beginA][beginB + 1];
			if (d2 == 0) {
				d2 = distanceHelp(charArrayA, charArrayB, beginA, beginB + 1, endA, endB); 
			}
			int d3 = record[beginA + 1][beginB + 1];
			if (d3 == 0) {
				d3 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB); 
			}
			distance = min(d1, d2, d3) + 1;
		}
		record[beginA][beginB] = distance;
		return distance;
	}
	
	private static int min(int x, int...yy) {
		int m = x;
		for (int y : yy) {
			if (y < m) {
				m = y;
			}
		}
		return m;
	}
}