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

Question

我已经解决了这个问题，但无法提出通过所有测试用例的最有效的问题。它在 5 个测试用例中超时。

确定句子包含短语的所有单词
0：克里斯和詹妮弗今天早上吵架了
1：克里斯去度假
2：詹妮弗在监狱里

查询短语为
0：chris jennifer
1：jennifer
2：监狱

目标是为每个查询找到匹配句子的索引，如果不存在匹配的句子，则为 -1。单词的顺序无关紧要。

输出：
0
0 2
2

即第一个查询在句子 0 中有匹配的词，在句子 0 和 1 中有第二个匹配词，依此类推。

约束

• n：句子数

• m: prases 的数量

• n, m < 10^4

• 任何句子或查询短语中的单词数在 [1-10] 范围内

• 每个单词最多有 11 个字符

• 没有单词出现在超过 10 个句子中

• 每个单词仅由大小写字母组成

• 每个单词必须完全匹配——即喜欢和喜欢不匹配。

输入格式：

3
克里斯和詹妮弗今天早上吵架了
克里斯去度假
詹妮弗在监狱里
3
克里斯
詹妮弗
监狱

每个 3 代表句子或查询的数量。

---

以下是我尝试过的...

1.我的第一个解决方案：

1. 为每个句子制作 HashMap

2. 对于短语中的每个拆分单词：
   2-1。检查句子hashmap
   2-2中是否存在所有单词。如果是这样，则存储索引
   2-3。如果所有句子都不存在匹配的句子，则存储-1。

3. 打印结果

let p = 句子中
的最大单词数 let k = 查询中的最大单词数
Big O 是O(npk)

Answer 1

维护一个HashMap将Strings映射到Set<Int>.&nbsp;这个想法是跟踪给定单词出现在哪些句子中。我们使用集合而不是数组来支持有效地计算两个集合的交集。对于每个输入句子：将其分词成词，将当前句子的索引加入当前分词对应的Set中。对于每个查询短语：将其标记为单词。查询每个词对应的索引集取所有这些集合的交集。时间复杂度：假设每个句子有 10 个单词，构建 HashMap 的成本是 O(10N log N)。每个查询的成本是 O(10 * log(N))。

Answer 2

我有以下可能会加速的想法，它似乎与 Rishav 提出的类似：public static void main(String[] args) throws FileNotFoundException {&nbsp; &nbsp; &nbsp; &nbsp; Scanner sc = new Scanner(new FileInputStream("file.txt"));&nbsp; &nbsp; &nbsp; &nbsp; int numberOfSentences = Integer.parseInt(sc.nextLine());&nbsp; &nbsp; &nbsp; &nbsp; Set<Integer> sentences = new HashSet<Integer>();&nbsp; &nbsp; &nbsp; &nbsp; Map<String, Set<Integer>> words2Sentences = new HashMap<String, Set<Integer>>();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < numberOfSentences; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String words[] = sc.nextLine().split(" ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < words.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!words2Sentences.containsKey(words[j])) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; words2Sentences.put(words[j], new HashSet<Integer>());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; words2Sentences.get(words[j]).add(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sentences.add(i);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int numberOfPhrases = Integer.parseInt(sc.nextLine());&nbsp; &nbsp; &nbsp; &nbsp; List<Set<Integer>> phraseResults = new ArrayList<Set<Integer>>();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < numberOfPhrases; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<String> phrases = new HashSet<String>(Arrays.asList(sc.nextLine().split(" ")));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<Integer> result = new HashSet(sentences);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (String s : phrases) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.retainAll(words2Sentences.get(s));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; phraseResults.add(result);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for (Set<Integer> set : phraseResults) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Integer i : set) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }

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++){&nbsp; &nbsp; string temp = sentences[i];&nbsp; &nbsp; temp.push_back(' ');&nbsp; &nbsp; string word = "";&nbsp; &nbsp; for(int j=0;j<temp.length();j++){&nbsp; &nbsp; &nbsp; &nbsp; if(temp[j] == ' '){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; itr = m.find(word);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(itr == m.end()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; set<int> s;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s.insert(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m.insert({word,s});&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if(itr != m.end()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; itr->second.insert(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; word = "";&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; word.push_back(temp[j]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}// for(itr = m.begin();itr!= m.end();itr++){//&nbsp; &nbsp; &nbsp;cout<<itr->first <<" ";//&nbsp; &nbsp; &nbsp;for(auto f= itr->second.begin();f!= itr->second.end();f++){//&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cout<<*f<<" ";//&nbsp; &nbsp; &nbsp;}//&nbsp; &nbsp; &nbsp;cout<<endl;// }for(int i=0;i<phrases.size();i++){&nbsp; &nbsp; string temp = phrases[i];&nbsp; &nbsp; temp.push_back(' ');&nbsp; &nbsp; string word = "";&nbsp; &nbsp; int flag = 0;&nbsp; &nbsp; set<int> s1,s2,s3;&nbsp; &nbsp; for(int j=0;j<temp.length();j++){&nbsp; &nbsp; &nbsp; &nbsp; if(temp[j] == ' '){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // cout<<"yes";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; itr = m.find(word);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(itr == m.end()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag = 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if(itr != m.end()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(s1.empty()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s1 = itr->second;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; set_intersection(s1.begin(),s1.end(),itr->second.begin(),itr->second.end(),inserter(s3,s3.begin()));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s1 = s3;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s3.clear();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(s1.empty()){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag = 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // for(auto f=s1.begin();f!= s1.end();f++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp; &nbsp;cout<<*f<<" ";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // cout<<endl;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; word = "";&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; word.push_back(temp[j]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if(flag == 1){&nbsp; &nbsp; &nbsp; &nbsp; s1.clear();&nbsp; &nbsp; &nbsp; &nbsp; s1.insert(-1);&nbsp; &nbsp; &nbsp; &nbsp; v[i] = s1;&nbsp; &nbsp; &nbsp; &nbsp; flag = 0 ;&nbsp; &nbsp; }&nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; v[i] = s1;&nbsp; &nbsp; }&nbsp; &nbsp; s1.clear();&nbsp; &nbsp; s2.clear();&nbsp; &nbsp; 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++){&nbsp; &nbsp; set<int> :: iterator itr;&nbsp; &nbsp; for(itr = v[i].begin() ;itr != v[i].end();itr++){&nbsp; &nbsp; &nbsp; &nbsp; cout<<*itr<<" ";&nbsp; &nbsp; }&nbsp; &nbsp; cout<<endl;}// cout<<"finish"<<endl;}