[面试题求教]remove common phrases from each sentence - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

[面试题求教]remove common phrases from each sentence

[面试题求教]remove common phrases from each sentence# JobHunting - 待字闺中

h*22013-03-19 07:03

1 楼

请求:
Interview Question – Given a set of Sentences containing lower case letters
only, remove common phrases from each sentence. Here a phrase is defined by
3 or more consecutive words.
E.g:
S1 = "I my bye good";
S2 = "my bye good boy";
common phrase is: "my bye good"
so the two sentence become
S1 = "I";
s2 ="boy";
How about the following input ? S1 = "q a b c d a b c b c d e" S2 = "a b c d
e"
What's the output? Is it ok to the following output? S1 = "q" S2 = ""
Yup, your output is correct. This is because there are three common phrases,
ie: "a b c d", "a b c", and "b c d e".

n*r2013-03-19 07:03

2 楼

空格做token切词出来，然后hash，找公共的，然后再分别扫两个string，删除公共的
word就可以了吧

n*r2013-03-19 07:03

3 楼

public static void removeCommon(String[] s){
Set set = new HashSet();
Set commonSet = new HashSet();
String[] list1 = s[0].split("[ ]+");

for (String w : list1){
set.add(w);
}

String[] list2 = s[1].split("[ ]+");
StringBuilder sb = new StringBuilder();
for (String w : list2){
if (!set.contains(w))
sb.append(w + " ");
else
commonSet.add(w);
}
if(sb.length() > 0)
sb.deleteCharAt(sb.length()-1);
s[1] = sb.toString();
sb = new StringBuilder();
for (String w : list1){
if (!commonSet.contains(w))
sb.append(w + " ");
}
if(sb.length() > 0)
sb.deleteCharAt(sb.length()-1);
s[0] = sb.toString();
}

h*22013-03-19 07:03

4 楼

你这个方法只是去除了相同的word，但是我们要删除的是 3 or more consecutive
words. 我想到的是对每个sentence都保存到一个map中，然后再
从第一个sentence开始先找头三个word是否在剩下的所有的sentence中，不符合则接着
选第一个sentence的接下来的三个。总体感觉看上去可以实现，但是还是比较繁琐的
。

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

: public static void removeCommon(String[] s){
: Set set = new HashSet();
: Set commonSet = new HashSet();
: String[] list1 = s[0].split("[ ]+");
:
: for (String w : list1){
: set.add(w);
: }
:
: String[] list2 = s[1].split("[ ]+");

G*A2013-03-19 07:03

5 楼

"a b c" are considered as three words?

letters
by

【在 h******2 的大作中提到】

: 请求:
: Interview Question – Given a set of Sentences containing lower case letters
: only, remove common phrases from each sentence. Here a phrase is defined by
: 3 or more consecutive words.
: E.g:
: S1 = "I my bye good";
: S2 = "my bye good boy";
: common phrase is: "my bye good"
: so the two sentence become
: S1 = "I";

h*22013-03-19 07:03

6 楼

yes

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

: "a b c" are considered as three words?
:
: letters
: by