常用工具类算法

分类: ALGORITHM 发布于:

“你不解决问题，你和问题同归于寂。解决了问题，你和问题都明了起来”

比较两个字符串的异同

算法解析

具体做法

  • 分散<被比较>元素的序数到第一列

  • 分散<比较>元素的序数到第一行

  • 逐行比较

  • 比较规则: 比较左侧、上侧、左上角元素的大小，取最小值加1

  • 返回对角线元素的值

算法验证

TODO

Code Example

org.springframework.beans.PropertyMatches.java

``` private static int calculateStringDistance(String s1, String s2) { if (s1.isEmpty()) { return s2.length(); } if (s2.isEmpty()) { return s1.length(); } int d[][] = new int[s1.length() + 1][s2.length() + 1];

	for (int i = 0; i <= s1.length(); i++) {
		d[i][0] = i;
	}
	for (int j = 0; j <= s2.length(); j++) {
		d[0][j] = j;
	}

	for (int i = 1; i <= s1.length(); i++) {
		char s_i = s1.charAt(i - 1);
		for (int j = 1; j <= s2.length(); j++) {
			int cost;
			char t_j = s2.charAt(j - 1);
			if (s_i == t_j) {
				cost = 0;
			}
			else {
				cost = 1;
			}
			d[i][j] = Math.min(Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1),
					d[i - 1][j - 1] + cost);
		}
	}

	return d[s1.length()][s2.length()];
}
```