c******t
发帖数: 391 | 1 上周电面遇到了一道pattern match的实现，
boolean matchPattern(String s, String q)
其中，
s: "catdogcatdogapplecatdogapple",
p(pattern): "XYXYZXYZ"
要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
射成dog，apple对应Z，所以结果返回true，否则返回false。
其他限制条件有:
1) 输入都是alphabetical
2) 每个pattern对应的字符串长度大于1
面的时候完全没有切入点，感觉是得找到每个重复出现的最长prefix，存为candidate
mapping(X->cat, Y->dog, Z->apple)，然后再扫一遍原字符串进行匹配，这个思路对
么？ | d**********6
发帖数: 4434 | 2 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
第二个字符串也要运行一下最长的prefix才变成00101 | c******t
发帖数: 391 | 3 有道理啊，那这道题应该用什么思路入手呢？
【在 d**********6 的大作中提到】
: 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
: 第二个字符串也要运行一下最长的prefix才变成00101
| r****7
发帖数: 2282 | 4 哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| d**********6
发帖数: 4434 | 5 这个思路不对，因为你用longest prefix压缩的话，信息就丢失可能会判断错误
比如XYXYZXYZ这个pattern可以压缩为00101
但XYXYZXYZY你一压缩的话就是001013了，最后一个y被对待成一个新的pattern
我觉得可以这样，从pattern string，也就是q入手。假设X对应的长度为L1, Y对应长
度为L2，Z为L3如此类推
先从(L1,L2,L3)=(2,2,2)开始，然后判断目标string也就是s是否符合
符合的条件比较简单，比较对应位置的元素是否相等，
比如XYX这个pattern，因为假设L1=2, L2=2，所以s里面就会出现s[0]=s[5],s[1]=s[6]
，不相等就return false
判断函数写好以后，就变成一个空间搜索问题
从(L1,L2,L3)=(2,2,2)
(3,2,2)
(3,3,2)
(3,3,3)
...
...
这个问题就可以用别的算法来优化了
【在 c******t 的大作中提到】
: 有道理啊，那这道题应该用什么思路入手呢？
| d**********6
发帖数: 4434 | 6 我的这个思路要写起来比较麻烦，比较琐碎，面试期间40~50分钟不一定能写出来啊。
可能有更简单的办法 | h**********c
发帖数: 4120 | 7 哎呀，你这个题呀！
让我想起来linear diaophantine equations (show the big bulge)
还记得不？
我提醒你am+bn =c
想起来了吧！
"catdogcatdogapplecatdogapple"
XYXYZXYZ has 3X, 3Y, 2Z
Then solve linear system
3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
X,Y,Z is in bigz ( integer+) abelian group.
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| z***m
发帖数: 1602 | 8 这样的解有很多啊
1 1 11
1 3 8
1 5 5
1 7 2
2 2 8
2 4 5
2 6 2
3 1 8
3 3 5
3 5 2
4 2 5
4 4 2
5 1 5
5 3 2
6 2 2
7 1 2
然后一个个的试？
【在 h**********c 的大作中提到】
: 哎呀，你这个题呀！
: 让我想起来linear diaophantine equations (show the big bulge)
: 还记得不？
: 我提醒你am+bn =c
: 想起来了吧！
: "catdogcatdogapplecatdogapple"
: XYXYZXYZ has 3X, 3Y, 2Z
: Then solve linear system
: 3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
: X,Y,Z is in bigz ( integer+) abelian group.
| S***w
发帖数: 1014 | 9 题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map
, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsKey(p.charAt(0))) {
if (p_to_s.get(p.charAt(0)) == pre &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else {
s_to_p.put(pre, p.charAt(0));
p_to_s.put(p.charAt(0), pre);
if (dfs(s.substring(i), p.substring(1), s_to_p, p_to_s)) return true;
s_to_p.remove(pre);
p_to_s.remove(p.charAt(0));
}
}
return false;
}
boolean solve(String s, String p) {
return dfs(s, p, new HashMap(), new HashMap
, String>());
}
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| h**********c
发帖数: 4120 | 10 filter XYXY first
2*X + 2*Y + 3*Z= LENGTH will have only one unkown.
maybe just try optimize it.
【在 z***m 的大作中提到】
: 这样的解有很多啊
: 1 1 11
: 1 3 8
: 1 5 5
: 1 7 2
: 2 2 8
: 2 4 5
: 2 6 2
: 3 1 8
: 3 3 5
| | | U***A
发帖数: 849 | 11 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.insert(make_pair(q[pos2], s1));
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
mp.erase(q[pos2]);
}
else{
if(mp[q[pos2]] == s1){
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
}
}
}
return false;
}
bool matchPattern(string s, string q){
int len1= (int)s.length();
if(len1 ==0) return false;
int len2=(int) q.length();
if(len2==0) return false;
map mp;
return matchPatternHelper(s, 0, q, 0, mp);
} | c******t
发帖数: 391 | 12 上周电面遇到了一道pattern match的实现，
boolean matchPattern(String s, String q)
其中，
s: "catdogcatdogapplecatdogapple",
p(pattern): "XYXYZXYZ"
要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
射成dog，apple对应Z，所以结果返回true，否则返回false。
其他限制条件有:
1) 输入都是alphabetical
2) 每个pattern对应的字符串长度大于1
面的时候完全没有切入点，感觉是得找到每个重复出现的最长prefix，存为candidate
mapping(X->cat, Y->dog, Z->apple)，然后再扫一遍原字符串进行匹配，这个思路对
么？ | d**********6
发帖数: 4434 | 13 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
第二个字符串也要运行一下最长的prefix才变成00101 | c******t
发帖数: 391 | 14 有道理啊，那这道题应该用什么思路入手呢？
【在 d**********6 的大作中提到】
: 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
: 第二个字符串也要运行一下最长的prefix才变成00101
| r****7
发帖数: 2282 | 15 哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| d**********6
发帖数: 4434 | 16 这个思路不对，因为你用longest prefix压缩的话，信息就丢失可能会判断错误
比如XYXYZXYZ这个pattern可以压缩为00101
但XYXYZXYZY你一压缩的话就是001013了，最后一个y被对待成一个新的pattern
我觉得可以这样，从pattern string，也就是q入手。假设X对应的长度为L1, Y对应长
度为L2，Z为L3如此类推
先从(L1,L2,L3)=(2,2,2)开始，然后判断目标string也就是s是否符合
符合的条件比较简单，比较对应位置的元素是否相等，
比如XYX这个pattern，因为假设L1=2, L2=2，所以s里面就会出现s[0]=s[5],s[1]=s[6]
，不相等就return false
判断函数写好以后，就变成一个空间搜索问题
从(L1,L2,L3)=(2,2,2)
(3,2,2)
(3,3,2)
(3,3,3)
...
...
这个问题就可以用别的算法来优化了
【在 c******t 的大作中提到】
: 有道理啊，那这道题应该用什么思路入手呢？
| d**********6
发帖数: 4434 | 17 我的这个思路要写起来比较麻烦，比较琐碎，面试期间40~50分钟不一定能写出来啊。
可能有更简单的办法 | h**********c
发帖数: 4120 | 18 哎呀，你这个题呀！
让我想起来linear diaophantine equations (show the big bulge)
还记得不？
我提醒你am+bn =c
想起来了吧！
"catdogcatdogapplecatdogapple"
XYXYZXYZ has 3X, 3Y, 2Z
Then solve linear system
3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
X,Y,Z is in bigz ( integer+) abelian group.
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| z***m
发帖数: 1602 | 19 这样的解有很多啊
1 1 11
1 3 8
1 5 5
1 7 2
2 2 8
2 4 5
2 6 2
3 1 8
3 3 5
3 5 2
4 2 5
4 4 2
5 1 5
5 3 2
6 2 2
7 1 2
然后一个个的试？
【在 h**********c 的大作中提到】
: 哎呀，你这个题呀！
: 让我想起来linear diaophantine equations (show the big bulge)
: 还记得不？
: 我提醒你am+bn =c
: 想起来了吧！
: "catdogcatdogapplecatdogapple"
: XYXYZXYZ has 3X, 3Y, 2Z
: Then solve linear system
: 3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
: X,Y,Z is in bigz ( integer+) abelian group.
| S***w
发帖数: 1014 | 20 题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map
, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsKey(p.charAt(0))) {
if (p_to_s.get(p.charAt(0)) == pre &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else {
s_to_p.put(pre, p.charAt(0));
p_to_s.put(p.charAt(0), pre);
if (dfs(s.substring(i), p.substring(1), s_to_p, p_to_s)) return true;
s_to_p.remove(pre);
p_to_s.remove(p.charAt(0));
}
}
return false;
}
boolean solve(String s, String p) {
return dfs(s, p, new HashMap(), new HashMap
, String>());
}
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| | | h**********c
发帖数: 4120 | 21 filter XYXY first
2*X + 2*Y + 3*Z= LENGTH will have only one unkown.
maybe just try optimize it.
【在 z***m 的大作中提到】
: 这样的解有很多啊
: 1 1 11
: 1 3 8
: 1 5 5
: 1 7 2
: 2 2 8
: 2 4 5
: 2 6 2
: 3 1 8
: 3 3 5
| U***A
发帖数: 849 | 22 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.insert(make_pair(q[pos2], s1));
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
mp.erase(q[pos2]);
}
else{
if(mp[q[pos2]] == s1){
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
}
}
}
return false;
}
bool matchPattern(string s, string q){
int len1= (int)s.length();
if(len1 ==0) return false;
int len2=(int) q.length();
if(len2==0) return false;
map mp;
return matchPatternHelper(s, 0, q, 0, mp);
} | t******5
发帖数: 30 | 23 mark 这个暴力解法，暂时想不到更好的
Character
【在 S***w 的大作中提到】
: 题目好难
: dfs暴力试吧
: boolean dfs(String s, String p, Map s_to_p, Map: , String> p_to_s) {
: if (s.isEmpty() && p.isEmpty()) return true;
: if (s.isEmpty() || p.isEmpty()) return false;
: for(int i = 2; i <= s.length(); ++i) {
: String pre = s.substring(0, i);
: if (s_to_p.containsKey(pre)) {
: if (s_to_p.get(pre) == p.charAt(0) &&
| x*******9
发帖数: 138 | 24 ++@heteroclinic
如果pattern少的话，就枚举XYZ的长度，顺序验证一下就好了。。。
我觉得这个最起码是一个60分的答案 | x*******9
发帖数: 138 | 25 想了半天，还是没有好方法。。。
如果是在OJ上的话，pattern < 5, strlen < 500，这题我就敢枚举每个pattern长度来
暴力搞
如果数据规模更大的话，可能会更难 | F****n
发帖数: 3271 | 26 dfs
First match abb with Len(a)>1 Len(b) > 2
If true check if b = az
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
| s*********u
发帖数: 18 | 27 Mark this interesting problem. | w****k
发帖数: 755 | | x**1
发帖数: 892 | 29
mark
【在 F****n 的大作中提到】
: dfs
: First match abb with Len(a)>1 Len(b) > 2
: If true check if b = az
| j**********0
发帖数: 20 | | | | h****n
发帖数: 1093 | 31 大爷的 这个题用来做电面? 哪个面试官这么变态 故意黑你吧
【在 c******t 的大作中提到】
: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1
|
|
