g***a
发帖数: 58 | 1 Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
请教有没有什么好的思路？
Given a pattern and a string input - find if the string follows the same
pattern and return 0 or 1.
Examples:
1) Pattern : "abab", input: "redblueredblue" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0. |
s**********r
发帖数: 34 | 2 一个星期前面过原题，用DFS做。
注意有可能会有这样的case:
"abab" input "redredredred" should return false
我当时用hashset存已经map过的pattern.
的,
【在 g***a 的大作中提到】
: Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
: 请教有没有什么好的思路？
: Given a pattern and a string input - find if the string follows the same
: pattern and return 0 or 1.
: Examples:
: 1) Pattern : "abab", input: "redblueredblue" should return 1.
: 2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
: 3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
|
g***a
发帖数: 58 | 3 多谢！
请问DFS是穷举法的意思么？
比如对于第一个pattern“a”的话遍历所有可能的子串长度？然后一直recursion，里
面加一个hashset的参数存当前出现过的所有pattern？
这样可以过test么？
【在 s**********r 的大作中提到】
: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,
|
s**********r
发帖数: 34 | 4 是的，有点像穷举法的感觉。
我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
上自己测试通过。
如果真的出这道题，你就不用那么紧张。
另外loghit那道也要准备，非常高频。
加油。 |
n**s
发帖数: 3 | 5 题目不是很清楚，
如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
【在 s**********r 的大作中提到】
: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,
|
e*******i
发帖数: 56 | 6 who can post a solution for the pattern matching problem. I have no clue. |
s********l
发帖数: 998 | 7 请问那个loghit啊
能给个link 或者说说题吗？
【在 s**********r 的大作中提到】
: 是的，有点像穷举法的感觉。
: 我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
: 上自己测试通过。
: 如果真的出这道题，你就不用那么紧张。
: 另外loghit那道也要准备，非常高频。
: 加油。
|
g***a
发帖数: 58 | 8 Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
请教有没有什么好的思路？
Given a pattern and a string input - find if the string follows the same
pattern and return 0 or 1.
Examples:
1) Pattern : "abab", input: "redblueredblue" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0. |
s**********r
发帖数: 34 | 9 一个星期前面过原题，用DFS做。
注意有可能会有这样的case:
"abab" input "redredredred" should return false
我当时用hashset存已经map过的pattern.
的,
【在 g***a 的大作中提到】
: Glassdoor上有人贴，不过上面没有详细的题目描述，不知道pattern是不是general的,
: 请教有没有什么好的思路？
: Given a pattern and a string input - find if the string follows the same
: pattern and return 0 or 1.
: Examples:
: 1) Pattern : "abab", input: "redblueredblue" should return 1.
: 2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
: 3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
|
g***a
发帖数: 58 | 10 多谢！
请问DFS是穷举法的意思么？
比如对于第一个pattern“a”的话遍历所有可能的子串长度？然后一直recursion，里
面加一个hashset的参数存当前出现过的所有pattern？
这样可以过test么？
【在 s**********r 的大作中提到】
: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,
|
|
|
s**********r
发帖数: 34 | 11 是的，有点像穷举法的感觉。
我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
上自己测试通过。
如果真的出这道题，你就不用那么紧张。
另外loghit那道也要准备，非常高频。
加油。 |
n**s
发帖数: 3 | 12 题目不是很清楚，
如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
【在 s**********r 的大作中提到】
: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,
|
e*******i
发帖数: 56 | 13 who can post a solution for the pattern matching problem. I have no clue. |
s********l
发帖数: 998 | 14 请问那个loghit啊
能给个link 或者说说题吗？
【在 s**********r 的大作中提到】
: 是的，有点像穷举法的感觉。
: 我给你一个建议：你可以先把带space的情况和不带space的情况自己先写一下，在电脑
: 上自己测试通过。
: 如果真的出这道题，你就不用那么紧张。
: 另外loghit那道也要准备，非常高频。
: 加油。
|
g*****y
发帖数: 1120 | 15 嗯， 出题人没想好。全解此题貌似要用到compiler技术。
【在 n**s 的大作中提到】
: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
|
g***a
发帖数: 58 | 16 那个例子貌似不合适，应该是输出1，
不过楼主的意思很明确，就是不同的pattern不能map到相同的string
比如pattern “abba” 对应 string “xxxx”就不行。
【在 n**s 的大作中提到】
: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
|
E****c
发帖数: 4 | 17 难道是这个？
http://www.mitbbs.com/article_t/JobHunting/32549839.html
【在 s********l 的大作中提到】
: 请问那个loghit啊
: 能给个link 或者说说题吗？
|
b********7
发帖数: 3 | 18 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗? |
w*******i
发帖数: 186 | 19 让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
return dfs(str, start1 + 下个单词长度,
pattern, start2, map, visited);
} else {
for (int end = start1 + 1; end <= str.length(); ++end) {
让nextWord为start1和end之间的substring,
if(nextWord在visited中) continue;
map.put(ch, nextWord);
visited.add(nextWord);
if (haveWordPattern(str, end, pattern, start2, map, visited)
) {
return true;
}
map.remove(ch);
visited.remove(nextWord);
}
return false;
}
其实里面还可以加点剪枝代码，不过大概就是这样了。
【在 b********7 的大作中提到】
: 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
: 那位大牛能给个多项式复杂度的算法吗?
|
m*******g
发帖数: 410 | |
|
|
g*****y
发帖数: 1120 | 21 嗯， 出题人没想好。全解此题貌似要用到compiler技术。
【在 n**s 的大作中提到】
: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
|
g***a
发帖数: 58 | 22 那个例子貌似不合适，应该是输出1，
不过楼主的意思很明确，就是不同的pattern不能map到相同的string
比如pattern “abba” 对应 string “xxxx”就不行。
【在 n**s 的大作中提到】
: 题目不是很清楚，
: 如果 a -> redr, b -> ed, abab 应该可以map 到 redredredred 吧？
|
E****c
发帖数: 4 | 23 难道是这个？
http://www.mitbbs.com/article_t/JobHunting/32549839.html
【在 s********l 的大作中提到】
: 请问那个loghit啊
: 能给个link 或者说说题吗？
|
b********7
发帖数: 3 | 24 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗? |
w*******i
发帖数: 186 | 25 让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.
boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set visited) {
if (start1 == str.length() || start2 == pattern.length) {
return start1 == str.length() && start2 == pattern.length;
}
char ch = pattern[start2++];
if (map.containsKey(ch)) {
在map里找到对应单词
if(str能够从start1开始取到这个单词）
return dfs(str, start1 + 下个单词长度,
pattern, start2, map, visited);
} else {
for (int end = start1 + 1; end <= str.length(); ++end) {
让nextWord为start1和end之间的substring,
if(nextWord在visited中) continue;
map.put(ch, nextWord);
visited.add(nextWord);
if (haveWordPattern(str, end, pattern, start2, map, visited)
) {
return true;
}
map.remove(ch);
visited.remove(nextWord);
}
return false;
}
其实里面还可以加点剪枝代码，不过大概就是这样了。
【在 b********7 的大作中提到】
: 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
: 那位大牛能给个多项式复杂度的算法吗?
|
m*******g
发帖数: 410 | |
h****n
发帖数: 643 | 27 这个应该是true的，re|dred|re|dred
【在 s**********r 的大作中提到】
: 一个星期前面过原题，用DFS做。
: 注意有可能会有这样的case:
: "abab" input "redredredred" should return false
: 我当时用hashset存已经map过的pattern.
:
: 的,
|
