集思广益 马飚 的 bar raiser 题

亚麻的bar raiser 题，似曾相识 发上来集思广益

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

后输出生成的合法数量

楼主相符如下，
1. brute force对input string进行两个字母的swap，每次判断这个字符是否在字典中
2. 字典如果不大的话，就做一个preprocessing，加一个叫 isValidPrefix 这样的方法，如果input string的prefix已经是不合法的了，后面无论怎么swap都是不合法

确定不是swap 2 substring？是的话有点像lc scramble string。 如果只是swap 两个字母，字典小的话能否先用map筛选出来anagram然后比较？

rogerlove7 发表于 2017-8-27 01:43
确定不是swap 2 substring？是的话有点像lc scramble string。 如果只是swap 两个字母，字典小的话能否先用 ...

就是两个字母，字典小就做pre-processing + filtering，这个好理解

rogerlove7 发表于 2017-8-27 01:43
确定不是swap 2 substring？是的话有点像lc scramble string。 如果只是swap 两个字母，字典小的话能否先用 ...

就是两个字母，字典小就做preprocessing + filtering，这个好理解

rogerlove7 发表于 2017-8-27 01:43
确定不是swap 2 substring？是的话有点像lc scramble string。 如果只是swap 两个字母，字典小的话能否先用 ...

就是两个字母，字典小就做preprocessing + filtering，这个好理解

rogerlove7 发表于 2017-8-27 01:43
确定不是swap 2 substring？是的话有点像lc scramble string。 如果只是swap 两个字母，字典小的话能否先用 ...

就是两个字母，字典小就做pre-processing + filtering，这个好理解

主要觉得字典很大，字符短， 所以首先想到吧字典弄成trie, 把string swap 两个字符。挨个找。

补充内容 (2017-8-27 03:14):
“如果input string的prefix已经是不合法的了，后面无论怎么swap都是不合法
” 对啊对啊

1) 暴力解：输入字符串两两swap， 然后看结果是否在字典中。
2) 看每一个字典中的单词和输入是否是2-edit away， 并且查看2-edit是否是swap得到。

复杂度不好说，根据字典和输入的长度不同各有千秋。