编程之美-计算字符串的相似度
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;char[] charArrayA = strA.toCharArray();char[] charArrayB = strB.toCharArray();distance = distanceHelp(charArrayA, charArrayB, 0, 0, lenA - 1, lenB - 1);}}return distance;}//endA和endB是不变的，因此记录子问题的解可用record来表示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=Breturn 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 == charArrayB) {distance = record;if (distance == 0) {distance = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB);}} else {int d1 = record;if (d1 == 0) {d1 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB, endA, endB); }int d2 = record;if (d2 == 0) {d2 = distanceHelp(charArrayA, charArrayB, beginA, beginB + 1, endA, endB); }int d3 = record;if (d3 == 0) {d3 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB); }distance = min(d1, d2, d3) + 1;}record = 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;}}
页:
[1]