面试题：查询 - 哪些句子包含一个短语的所有单词

Question

我已经解决了这个问题，但无法提出通过所有测试用例的最有效的问题。它在 5 个测试用例中超时。确定句子包含短语的所有单词0：克里斯和詹妮弗今天早上吵架了1：克里斯去度假2：詹妮弗在监狱里查询短语为0：chris jennifer1：jennifer2：监狱目标是为每个查询找到匹配句子的索引，如果不存在匹配的句子，则为 -1。单词的顺序无关紧要。输出：00 22即第一个查询在句子 0 中有匹配的词，在句子 0 和 1 中有第二个匹配词，依此类推。约束n：句子数m: prases 的数量n, m < 10^4任何句子或查询短语中的单词数在 [1-10] 范围内每个单词最多有 11 个字符没有单词出现在超过 10 个句子中每个单词仅由大小写字母组成每个单词必须完全匹配——即喜欢和喜欢不匹配。输入格式：3克里斯和詹妮弗今天早上吵架了克里斯去度假詹妮弗在监狱里3克里斯詹妮弗监狱每个 3 代表句子或查询的数量。以下是我尝试过的...1.我的第一个解决方案：为每个句子制作 HashMap对于短语中的每个拆分单词：2-1。检查句子hashmap2-2中是否存在所有单词。如果是这样，则存储索引2-3。如果所有句子都不存在匹配的句子，则存储-1。打印结果let p = 句子中的最大单词数 let k = 查询中的最大单词数Big O 是O(npk)

Answer 1

维护一个HashMap将Strings映射到Set<Int>. 这个想法是跟踪给定单词出现在哪些句子中。我们使用集合而不是数组来支持有效地计算两个集合的交集。

对于每个输入句子：

• 将其分词成词，将当前句子的索引加入当前分词对应的Set中。

对于每个查询短语：

• 将其标记为单词。

• 查询每个词对应的索引集

• 取所有这些集合的交集。

时间复杂度：假设每个句子有 10 个单词，构建 HashMap 的成本是 O(10N log N)。每个查询的成本是 O(10 * log(N))。

Answer 2

我有以下可能会加速的想法，它似乎与 Rishav 提出的类似：

public static void main(String[] args) throws FileNotFoundException {

        Scanner sc = new Scanner(new FileInputStream("file.txt"));

        int numberOfSentences = Integer.parseInt(sc.nextLine());

        Set<Integer> sentences = new HashSet<Integer>();

        Map<String, Set<Integer>> words2Sentences = new HashMap<String, Set<Integer>>();

        for (int i = 0; i < numberOfSentences; i++) {

            String words[] = sc.nextLine().split(" ");

            for (int j = 0; j < words.length; j++) {

                if (!words2Sentences.containsKey(words[j])) {

                    words2Sentences.put(words[j], new HashSet<Integer>());

                }

                words2Sentences.get(words[j]).add(i);

            }

            sentences.add(i);

        }

        int numberOfPhrases = Integer.parseInt(sc.nextLine());

        List<Set<Integer>> phraseResults = new ArrayList<Set<Integer>>();

        for (int i = 0; i < numberOfPhrases; i++) {

            Set<String> phrases = new HashSet<String>(Arrays.asList(sc.nextLine().split(" ")));

            Set<Integer> result = new HashSet(sentences);

            for (String s : phrases) {

                result.retainAll(words2Sentences.get(s));

            }

            phraseResults.add(result);

        }

        for (Set<Integer> set : phraseResults) {

            for (Integer i : set) {

                System.out.print(i);

            }

            System.out.println();

        }

    }

Answer 3

这种方法应该有效。

#include <bits/stdc++.h>

using namespace std;

vector<set<int>> getres(vector<string> sentences, vector<string> phrases, vector<set<int>> v){

map<string,set<int>> m;

map<string,set<int>> :: iterator itr;

for(int i=0;i<sentences.size();i++){

    string temp = sentences[i];

    temp.push_back(' ');

    string word = "";

    for(int j=0;j<temp.length();j++){

        if(temp[j] == ' '){

            itr = m.find(word);

            if(itr == m.end()){

                set<int> s;

                s.insert(i);

                m.insert({word,s});

            }

            else if(itr != m.end()){

                itr->second.insert(i);

            }

            word = "";

        }

        else{

            word.push_back(temp[j]);

        }

    }

}

// for(itr = m.begin();itr!= m.end();itr++){

//     cout<<itr->first <<" ";

//     for(auto f= itr->second.begin();f!= itr->second.end();f++){

//         cout<<*f<<" ";

//     }

//     cout<<endl;

// }

for(int i=0;i<phrases.size();i++){

    string temp = phrases[i];

    temp.push_back(' ');

    string word = "";

    int flag = 0;

    set<int> s1,s2,s3;

    for(int j=0;j<temp.length();j++){

        if(temp[j] == ' '){

            // cout<<"yes";

            itr = m.find(word);

            if(itr == m.end()){

                flag = 1;

                break;

            }

            else if(itr != m.end()){

                if(s1.empty()){

                    s1 = itr->second;

                }

                else{

                    set_intersection(s1.begin(),s1.end(),itr->second.begin(),itr->second.end(),inserter(s3,s3.begin()));

                    s1 = s3;

                    s3.clear();

                    if(s1.empty()){

                        flag = 1;

                        break;

                    }

                }

                // for(auto f=s1.begin();f!= s1.end();f++){

                //     cout<<*f<<" ";

                // }

                // cout<<endl;

            }

            word = "";

        }

        else{

            word.push_back(temp[j]);

        }

    }

    if(flag == 1){

        s1.clear();

        s1.insert(-1);

        v[i] = s1;

        flag = 0 ;

    }

    else{

        v[i] = s1;

    }

    s1.clear();

    s2.clear();

    s3.clear();

}

return v;

}

int main() {

vector<string> sentences = {"chris and jennifer had a fight this morning", "chris went on a holiday", "jennifer is in prison"};

vector<string> phrases = {"chris jennifer", "jennifer", "prison"};

vector<set<int>> v(phrases.size());

v = getres(sentences,phrases,v);

for(int i=0;i<v.size();i++){

    set<int> :: iterator itr;

    for(itr = v[i].begin() ;itr != v[i].end();itr++){

        cout<<*itr<<" ";

    }

    cout<<endl;

}

// cout<<"finish"<<endl;

}