【每日一题】- 2019-08-29 - 854. 相似度为 K 的字符串

[azl397985856]

【每日一题】- 2019-08-29 - 854. 相似度为 K 的字符串

[xiongcaihu]

/**
 * 
 * 思路：挨个遍历A，如果当前位置i，A[i]!=B[i]，则开始交换，
 * 交换时，需要将A[j] = B[i] 的元素放在i位置，注意，这里j可能有多个值，所以需要来个循环
 * 还有个要注意的是：如果A[j]=B[i] && A[j] == B[j] 这种情况，是不需要交换的
 * 举个例子：
 * abcb bbca ，第一个交换位置是0，这个时候，有两个选择，把A[1]或A[3]换到0位置，那么如果是位置1，这个时候本来A[1]和B[1]就相等，如果换了，就要多一次交换次数
 * 所以这里我们只选择交换A[3]
 * 
 * 另外，在处理循环时，要注意，如果交换j1时，会得到后面一系列的结果，这时，可以将这些结果保存起来，
 * 如果在交换j2时，遇到已经处理过的结果，就直接调用
 * 
 * 这里我用递归做，思路应该会清晰点
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var kSimilarity = function(A, B) {
	var map = {};

	return temp(0, A);

	function temp(start, tA) {
		if (start == tA.length) {
			return 0;
		}
		if (map[tA]) {
			return map[tA];
		}
		if (tA[start] == B[start]) {
			return temp(start + 1, tA);
		} else {
			var min = Infinity;
			for (var i = start + 1; i < tA.length; i++) {
				if (tA[i] == B[start] && tA[i] != B[i]) {
					var newA =
						tA.substring(0, start) +
						tA[i] +
						tA.substring(start + 1, i) +
						tA[start] +
						tA.substring(i + 1);
					min = Math.min(min, 1 + temp(start + 1, newA));
				}
			}
			map[tA] = min;
			return min;
		}
	}
};

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.