JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2024-03-24
目录

相似度为 K 的字符串Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

对于某些非负整数 k ,如果交换 s1 中两个字母的位置恰好 k 次,能够使结果字符串等于 s2 ,则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ,返回 s1 和 s2 的相似度 k 的最小值。

示例 1:

输入:s1 = "ab", s2 = "ba"
输出:1

示例 2:

输入:s1 = "abc", s2 = "bca"
输出:2

提示:

  • 1 <= s1.length <= 20
  • s2.length == s1.length
  • s1 和 s2 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
  • s2 是 s1 的一个字母异位词

# 思路

dfs + 剪枝

# 解法

class Solution {
    int min = Integer.MAX_VALUE;
    public int kSimilarity(String s1, String s2) {
        dfs(s1.toCharArray(), s2.toCharArray(), 0, s1.length(), 0);
        return min;
    }
    private void dfs(char[] arr1, char[] arr2, int cur, int len, int count){
        if(cur == len){  // 当遍历完字符串,更新min 交换次数
            min = Math.min(min, count);
            return;
        }
        if(count >= min) return; // 剪枝
        if(arr1[cur] != arr2[cur]){
            for(int i = cur + 1; i < len; ++i){
                if(arr1[cur] == arr2[i]){
                    swap(arr2, cur, i);
                    dfs(arr1, arr2, cur + 1, len, count + 1);
                    swap(arr2, cur, i);
                }
            }
        }else {
            dfs(arr1, arr2, cur + 1, len, count);
        }
    }
    // 交换三连
    private void swap(char[] arr, int i, int j){
        char tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
}

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

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式