J**9
发帖数: 835 | 1 1) Uncommon words from two sentences
Example:
str1="this apple is sweet"
str2="that apple is sour"
Return words "this" "that" "sweet" "sour" since they only appear in one
string, not the other.
Extend: how about N sentences?
2) How to generate Query Snippets
User tries to query "wordA wordB" from a large text file
Return the shortest substring containg all queried words
Example:
Query "catch fish" from text "It's not easy to *catch a fish* in a fast-
flowing river while #fish can be easily catched# using a net from a static
lake"
There are two matches between ** and ##, the first one shall be returned
since it's shorter. |
J**9
发帖数: 835 | 2 Quick ideas:
1) Hash
2) Sliding window? |
q******6
发帖数: 1 | 3 1、 hashtable
2、 可以维护两个简单变量position indexA和position indexB
然后遍历txt文件的每个单词， 发现wordA或者wordB把当前的index更新到对应的
position indexA和position indexB上， 然后计算和position indexB或者position
indexA的值的差，然后记录一个minDiff的值来打擂台，时间复杂度O（n）空间复杂度O
（1）
2如果要求返回substring的可以记录最小距离的两个index，然后再遍历一遍txt文件来
找出substring |
J**9
发帖数: 835 | 4 Cool!
2) What if more than two words?
度O
【在 q******6 的大作中提到】
: 1、 hashtable
: 2、 可以维护两个简单变量position indexA和position indexB
: 然后遍历txt文件的每个单词， 发现wordA或者wordB把当前的index更新到对应的
: position indexA和position indexB上， 然后计算和position indexB或者position
: indexA的值的差，然后记录一个minDiff的值来打擂台，时间复杂度O（n）空间复杂度O
: （1）
: 2如果要求返回substring的可以记录最小距离的两个index，然后再遍历一遍txt文件来
: 找出substring
|
q******6
发帖数: 1 | 5 如果多于两个字符串就维护多个变量，然后找到一个word的时候把当前的index和多个
变量中最小的非0index求差打擂台
【在 J**9 的大作中提到】
: Cool!
: 2) What if more than two words?
:
: 度O
|
q******6
发帖数: 1 | |
J**9
发帖数: 835 | |
n********g
发帖数: 6504 | 8 1、排序，类似merge
2、LC有经典的，如果word N个你咋办
度O
【在 q******6 的大作中提到】
: 1、 hashtable
: 2、 可以维护两个简单变量position indexA和position indexB
: 然后遍历txt文件的每个单词， 发现wordA或者wordB把当前的index更新到对应的
: position indexA和position indexB上， 然后计算和position indexB或者position
: indexA的值的差，然后记录一个minDiff的值来打擂台，时间复杂度O（n）空间复杂度O
: （1）
: 2如果要求返回substring的可以记录最小距离的两个index，然后再遍历一遍txt文件来
: 找出substring
|
