当前位置:网站首页>854. 相似度为 K 的字符串 BFS
854. 相似度为 K 的字符串 BFS
2022-07-05 21:30:00 【钰娘娘】
854. 相似度为 K 的字符串
字符串
s1
和s2
是k
相似 的(对于某些非负整数k
),如果我们可以交换s1
中两个字母的位置正好k
次,使结果字符串等于s2
。给定两个字谜游戏
s1
和s2
,返回s1
和s2
与k
相似 的最小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一直超时,头疼
方法:BFS
1. 起点步数为0,化解为求a变成b的最少步数问题
2. 每次用其中某个相同字符进行填写,挪动到对应位置
3. 找到了直接返回
class Solution {
public int kSimilarity(String s1, String s2) {
Queue<String> queue = new LinkedList<>();
Map<String,Integer> distances = new HashMap<>();
distances.put(s1,0);
queue.offer(s1);
while (!queue.isEmpty()){
String str = queue.poll();
int nextStep = distances.get(str)+1;
for(String next:getNext(str,s2)){
if(next.equals(s2)) return nextStep;
if(!distances.containsKey(next)){
distances.put(next,nextStep);
queue.offer(next);
}
}
}
return 0;
}
private List<String> getNext(String s,String hope){
List<String> ans = new ArrayList<>();
char[] cs1 = s.toCharArray();
char[] cs2 = hope.toCharArray();
int n = cs1.length;
int i = 0;
while (i<n&&cs1[i]==cs2[i]) ++i;
for(int j = i+1; j < n; j++){
if(cs1[j]!=cs2[j]&&cs1[j]==cs2[i]){
swap(cs1,i,j);
ans.add(new String(cs1));
swap(cs1,i,j);
}
}
return ans;
}
private void swap(char[] cs, int i, int j){
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}
边栏推荐
- 显示屏DIN 4102-1 Class B1防火测试要求
- int GetMonth( ) const throw( ); What does throw () mean?
- What are the requirements of UL 2043 test for drive housing in the United States?
- Five layer network protocol
- Clion-MinGW编译后的exe文件添加ico图标
- Pytoch practice -- MNIST dataset handwritten digit recognition
- Using webassembly to operate excel on the browser side
- XML modeling
- 有些事情让感情无处安放
- Explain various hot issues of Technology (SLB, redis, mysql, Kafka, Clickhouse) in detail from the architecture
猜你喜欢
使用Aspect制作全局异常处理类
Ethereum ETH的奖励机制
MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
How to prepare for the algorithm interview and answer the algorithm interview questions
Simple interest mode - evil Chinese style
Influence of oscilloscope probe on measurement bandwidth
What should I do to prepare for the interview algorithm position during school recruitment?
Cross end solution to improve development efficiency rapidly
MySQL 千万数据量深分页优化, 拒绝线上故障!
PVC 塑料片BS 476-6 火焰传播性能测定
随机推荐
Talk about my fate with some programming languages
Incentive mechanism of Ethereum eth
基于vertx-web-sstore-redis的改造实现vertx http应用的分布式session
MQ----activeMq
字典树简单入门题(居然是蓝题?)
What should I do to prepare for the interview algorithm position during school recruitment?
Haas506 2.0 development tutorial - Alibaba cloud OTA - PAC firmware upgrade (only supports versions above 2.2)
Li Kou ----- the maximum profit of operating Ferris wheel
vant 源码解析 之深层 合并对象 深拷贝
postgis 安装地理信息扩展
selenium 获取dom内验证码图片
Utils/index TS tool function
@Validated basic parameter verification, grouping parameter verification and nested parameter verification
冯唐“春风十里不如你”数字藏品,7月8日登录希壤!
Gcc9.5 offline installation
Aitm 2-0003 horizontal combustion test
Parker驱动器维修COMPAX控制器维修CPX0200H
Establishment of terminal security capability verification environment and penetration test records
Prior knowledge of machine learning in probability theory (Part 1)
Realize the function of verifying whether the user has completed login when browsing the page