k****t
发帖数: 184 | 1 输入两个string,输出regular expression能够match这两个string，不能简单的输出一
个".*"，要尽量严格缩小范围。
String getRegex(String str1, String str2) {
...
}
我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
面试官说:"This is not a technically optimized solution."
给出的提示是，让我想想如果前缀相同，或者后缀相同的情况， 以及输入的是一个字
符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
请问，大家有没有什么好想法？ |
d********e
发帖数: 239 | 2 edit distance,差异部分 用二选一, 多出来的部分用?匹配
【在 k****t 的大作中提到】
: 输入两个string,输出regular expression能够match这两个string，不能简单的输出一
: 个".*"，要尽量严格缩小范围。
: String getRegex(String str1, String str2) {
: ...
: }
: 我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
: 面试官说:"This is not a technically optimized solution."
: 给出的提示是，让我想想如果前缀相同，或者后缀相同的情况， 以及输入的是一个字
: 符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
: 请问，大家有没有什么好想法？
|
m*****n
发帖数: 2152 | 3 考官的意思是不是这个：
str1 = "aaab"
str2 = "ab"
reg = "a*b" 而不是 "a.*b"
str1 = "aaabbb"
str2 = "ab"
reg = "a*b*" ?
【在 k****t 的大作中提到】
: 输入两个string,输出regular expression能够match这两个string，不能简单的输出一
: 个".*"，要尽量严格缩小范围。
: String getRegex(String str1, String str2) {
: ...
: }
: 我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
: 面试官说:"This is not a technically optimized solution."
: 给出的提示是，让我想想如果前缀相同，或者后缀相同的情况， 以及输入的是一个字
: 符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
: 请问，大家有没有什么好想法？
|
k****t
发帖数: 184 | 4 应该是后者，"."是需要的
【在 m*****n 的大作中提到】
: 考官的意思是不是这个：
: str1 = "aaab"
: str2 = "ab"
: reg = "a*b" 而不是 "a.*b"
: str1 = "aaabbb"
: str2 = "ab"
: reg = "a*b*" ?
|
m*****n
发帖数: 2152 | 5 我刚试了，前者是可以的，后者也可以。但是前者应该更优化。
【在 k****t 的大作中提到】
: 应该是后者，"."是需要的
|
M**********7
发帖数: 378 | 6 这题有点变态了。估计题的细节条件还是要扣细点。
广义来说正则文法是不可学习的。
简单的说就是到底允许不允许扩大结果范围，还是必须严格地只能匹配str1&str2。
如果允许扩大结果范围，那么.*和a*对于aa和a没什么不同，最简定义到底是什么。
如果不允许扩大结果范围，那么就按ksrent这样的思路，不同的时候用个|二选一，注
意不能用.。
【在 k****t 的大作中提到】
: 输入两个string,输出regular expression能够match这两个string，不能简单的输出一
: 个".*"，要尽量严格缩小范围。
: String getRegex(String str1, String str2) {
: ...
: }
: 我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
: 面试官说:"This is not a technically optimized solution."
: 给出的提示是，让我想想如果前缀相同，或者后缀相同的情况， 以及输入的是一个字
: 符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
: 请问，大家有没有什么好想法？
|
m*****n
发帖数: 2152 | 7 我猜想 最简定义是用的通配符最少。
比如 * 比 .* 简化， * 也比 .. 简化，.*比.....简化。
如果是这个思路，可以分两步，第一步用楼主的方法，第二部看看.* 能不能简化成 *
或者是. 。
但是还有问题没解决。
比如 "adabbccc" 和 "abbc"
reg = "a.*bbc*" 还是 ".*abbc*" ？ 两个好像都可以。
【在 M**********7 的大作中提到】
: 这题有点变态了。估计题的细节条件还是要扣细点。
: 广义来说正则文法是不可学习的。
: 简单的说就是到底允许不允许扩大结果范围，还是必须严格地只能匹配str1&str2。
: 如果允许扩大结果范围，那么.*和a*对于aa和a没什么不同，最简定义到底是什么。
: 如果不允许扩大结果范围，那么就按ksrent这样的思路，不同的时候用个|二选一，注
: 意不能用.。
|
k****t
发帖数: 184 | 8 那样的话 ".*"就全部搞定了。
【在 m*****n 的大作中提到】
: 我猜想 最简定义是用的通配符最少。
: 比如 * 比 .* 简化， * 也比 .. 简化，.*比.....简化。
: 如果是这个思路，可以分两步，第一步用楼主的方法，第二部看看.* 能不能简化成 *
: 或者是. 。
: 但是还有问题没解决。
: 比如 "adabbccc" 和 "abbc"
: reg = "a.*bbc*" 还是 ".*abbc*" ？ 两个好像都可以。
|
m*****n
发帖数: 2152 | 9 在“要尽量严格缩小范围”条件下，通配符最少。
换句话说，maximize common的字符， minimize 通配符 。
【在 k****t 的大作中提到】
: 那样的话 ".*"就全部搞定了。
|
s****a
发帖数: 794 | 10 正则表达式没法写吧，如果要严格的缩小范围那就是str1和str2两个pattern里选了。
只有这两个满足条件。我觉得要不就是他自己一知半解，被坑了，要不就是有别的条件
没注意到。 |
