LC.P854[相似度为 K 的字符串]

方法一：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int kSimilarity(String s1, String s2) {
        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s1);
        visited.add(s1);
        int ans = 0;
        while (true) {
            for (int i = queue.size(); i > 0; --i) {
                String s = queue.poll();
                if (s.equals(s2)) return ans;
                for (String t : next(s, s2)) {
                    if (!visited.contains(t)) {
                        visited.add(t);
                        queue.offer(t);
                    }
                }
            }
            ++ans;
        }
    }

    private List<String> next(String s, String s2) {
        int i = 0, n = s.length();
        char[] cs = s.toCharArray();
        
        while (cs[i] == s2.charAt(i)) ++i;

        List<String> res = new ArrayList<>();
        for (int j = i + 1; j < n; ++j) {
            if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) {
                swap(cs, i, j);
                res.add(new String(cs));
                swap(cs, i, j);
            }
        }
        return res;
    }

    private void swap(char[] cs, int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }
}

方法二：回溯+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int ans = Integer.MAX_VALUE;
    char[] cs1, cs2;

    public int kSimilarity(String s1, String s2) {
        cs1 =s1.toCharArray();
        cs2 = s2.toCharArray();
        return dfs(0, 0);
    }

    private int dfs(int start, int cur) {
        if (cur >= ans) return ans;
        if (start == cs1.length - 1) return ans = cur;

        for (int i = start; i < cs1.length; ++i) {
            if (cs1[i] != cs2[i]) {
                for (int j = i + 1; j < cs2.length; ++j) {
                    if (cs2[j] == cs1[i] && cs2[j] != cs1[j]) {
                        swap(cs2, i, j);
                        dfs(i + 1, cur + 1);
                        swap(cs2, i, j);
                        if (cs2[i] == cs1[j]) break;
                    }
                }
                return ans;
            }
        }
        return ans = cur;
    }

    private void swap(char[] cs, int i, int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}