854. 相似度为 K 的字符串.md

854. 相似度为 K 的字符串

题目传送门

点击这里

解题思路

这道题的难度比较大，方法也居多，暴力的dfs和bfs可以解决，但是耗时太长要进行优化，用的剪枝来做，这道题的动态规划和启发式搜索难度都比较大，了解下即可。剪枝的dfs和bfs的思路就是首先要有个结构体记录记录好更新过的s1和已经处理到的索引位置i，从i向后找到s1和s2不同的位置更新i，然后从i的后面继续找可以更换位置的字符s[j]，但是不要s[j] == s2[j]，这样子做没有意义，所以可以剪枝优化，更换后就记忆化记录然后记录新的s和i+1，回溯，回溯的目的是后面可能还有s2[j2]满足要求，然后继续遍历q。dfs的思路和bfs大致相同，但比bfs要考虑的多一点，具体写在注释。

代码

func kSimilarity(s1 string, s2 string) int {
	var res int
	// 构建结构体，s是更换过的字符串
	type pair struct {
		s string
		i int
	}
	q := []pair{{s1, 0}}
	// 记忆化
	m := map[string]bool{
		s1: true,
	}
	for n := len(s1); ; res++ {
		tmp := q
		q = nil
		for _, p := range tmp {
			s, i := p.s, p.i
			if s == s2 {
				return res
			}
			// 找到不相同的值
			for i < n && s[i] == s2[i] {
				i++
			}
			t := []byte(s)
			for j := i + 1; j < n; j++ {
				if s[j] == s2[i] && s[j] != s2[j] {
					// 剪枝，这一步是找到s后面有和s2[i]相同的值，但是要保证不和s2[j]相同，否则没有意义
					t[i], t[j] = t[j], t[i]
					if b := string(t); !m[b] {
						m[b] = true
						q = append(q, pair{b, i + 1})
					}
					// 再回溯
					t[i], t[j] = t[j], t[i]
				}
			}
		}
	}
}

func kSimilarity(s1, s2 string) int {
    var s, t []byte
    // 事先统计好不相同的字符
    for i := range s1 {
        if s1[i] != s2[i] {
            s = append(s, s1[i])
            t = append(t, s2[i])
        }
    }
    // 记录不相同字符的个数
    n := len(s)
    if n == 0 {
        return 0
    }
    // 这个可以推理得出，如果两个字符串数组中的字符可以通过换位交换最终得到一样的，且每一处的字符都不相同，那么最小的次数即为(diff + 1) / 2
    minSwap := func(i int) int {
        diff := 0
        for j := i; j < n; j++ {
            if s[j] != t[j] {
                diff++
            }
        }
        return (diff + 1) / 2
    }
    // 交换次数最多就是n-1次
    ans := n - 1
    var dfs func(int, int)
    dfs = func(i, cost int) {
        if cost > ans {
            return
        }
        for i < n && s[i] == t[i] {
            i++
        }
        if i == n {
            ans = min(ans, cost)
            return
        }
        // 当前状态的交换次数下限大于等于当前的最小交换次数
        if cost+minSwap(i) >= ans {
            return
        }
        // 找到不同的i+1，同样思路
        for j := i + 1; j < n; j++ {
            if s[j] == t[i] {
                s[i], s[j] = s[j], s[i]
                dfs(i+1, cost+1)
                s[i], s[j] = s[j], s[i]
            }
        }
    }
    dfs(0, 0)
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}