组里来了一个法国妞 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

组里来了一个法国妞

组里来了一个法国妞# Fashion - 美丽时尚

k*t2011-03-29 07:03

1 楼

输入两个string,输出regular expression能够match这两个string，不能简单的输出一
个".*"，要尽量严格缩小范围。
String getRegex(String str1, String str2) {
...
}
我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
面试官说:"This is not a technically optimized solution."
给出的提示是，让我想想如果前缀相同，或者后缀相同的情况，以及输入的是一个字
符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
请问，大家有没有什么好想法？

G*32011-03-29 07:03

2 楼

高高的，大概1米8左右，长得也不错~第一眼看到的就是她的longchamp，国民包啊！

d*e2011-03-29 07:03

3 楼

edit distance,差异部分用二选一, 多出来的部分用?匹配

【在 k****t 的大作中提到】

: 输入两个string,输出regular expression能够match这两个string，不能简单的输出一
: 个".*"，要尽量严格缩小范围。
: String getRegex(String str1, String str2) {
: ...
: }
: 我当时能想到的办法是，先找到共同的部分，然后中间插入".*"连成一个串。
: 面试官说:"This is not a technically optimized solution."
: 给出的提示是，让我想想如果前缀相同，或者后缀相同的情况，以及输入的是一个字
: 符串集合。然后就没有其他提示了。后来时间也不够，就结束了。
: 请问，大家有没有什么好想法？

b*s2011-03-29 07:03

4 楼

almost all girls and women carry Longchamp in Paris. in all colors and all s
izes. :)

【在 G******3 的大作中提到】

: 高高的，大概1米8左右，长得也不错~第一眼看到的就是她的longchamp，国民包啊！

m*n2011-03-29 07:03

5 楼

考官的意思是不是这个：
str1 = "aaab"
str2 = "ab"
reg = "a*b" 而不是 "a.*b"
str1 = "aaabbb"
str2 = "ab"
reg = "a*b*" ?

【在 k****t 的大作中提到】

k*t2011-03-29 07:03

6 楼

应该是后者，"."是需要的

【在 m*****n 的大作中提到】

: 考官的意思是不是这个：
: str1 = "aaab"
: str2 = "ab"
: reg = "a*b" 而不是 "a.*b"
: str1 = "aaabbb"
: str2 = "ab"
: reg = "a*b*" ?

m*n2011-03-29 07:03

7 楼

我刚试了，前者是可以的，后者也可以。但是前者应该更优化。

【在 k****t 的大作中提到】

: 应该是后者，"."是需要的

M*72011-03-29 07:03

8 楼

这题有点变态了。估计题的细节条件还是要扣细点。
广义来说正则文法是不可学习的。
简单的说就是到底允许不允许扩大结果范围，还是必须严格地只能匹配str1&str2。
如果允许扩大结果范围，那么.*和a*对于aa和a没什么不同，最简定义到底是什么。
如果不允许扩大结果范围，那么就按ksrent这样的思路，不同的时候用个|二选一，注
意不能用.。

【在 k****t 的大作中提到】

m*n2011-03-29 07:03

9 楼

我猜想最简定义是用的通配符最少。
比如 * 比 .* 简化， * 也比 .. 简化，.*比.....简化。
如果是这个思路，可以分两步，第一步用楼主的方法，第二部看看.* 能不能简化成 *
或者是. 。
但是还有问题没解决。
比如 "adabbccc" 和 "abbc"
reg = "a.*bbc*" 还是 ".*abbc*" ？两个好像都可以。

【在 M**********7 的大作中提到】

: 这题有点变态了。估计题的细节条件还是要扣细点。
: 广义来说正则文法是不可学习的。
: 简单的说就是到底允许不允许扩大结果范围，还是必须严格地只能匹配str1&str2。
: 如果允许扩大结果范围，那么.*和a*对于aa和a没什么不同，最简定义到底是什么。
: 如果不允许扩大结果范围，那么就按ksrent这样的思路，不同的时候用个|二选一，注
: 意不能用.。

k*t2011-03-29 07:03

10 楼

那样的话 ".*"就全部搞定了。

【在 m*****n 的大作中提到】

: 我猜想最简定义是用的通配符最少。
: 比如 * 比 .* 简化， * 也比 .. 简化，.*比.....简化。
: 如果是这个思路，可以分两步，第一步用楼主的方法，第二部看看.* 能不能简化成 *
: 或者是. 。
: 但是还有问题没解决。
: 比如 "adabbccc" 和 "abbc"
: reg = "a.*bbc*" 还是 ".*abbc*" ？两个好像都可以。

m*n2011-03-29 07:03

11 楼

在“要尽量严格缩小范围”条件下，通配符最少。
换句话说，maximize common的字符， minimize 通配符。

【在 k****t 的大作中提到】

: 那样的话 ".*"就全部搞定了。