给定两个列表句子和列表查询
我有两个查找句子中查询出现的情况。
示例,
“Pulkit 喜欢 StackOverflow 和编码”
“Pulkit 不喜欢 Reddit”
“像冰淇淋一样的果肉”
查询
Pulkit 编码
喜欢
是
该函数应返回查询
句子[0]
句子[1]、句子[2]
句子[1]
我已经使用 HashMap 解决了这个问题,但它是二次的,我想知道如何在线性时间内完成它。
解决方案
public static void findMatch(List<String> sentences, List<String> queries) {
// Write your code here
// Split the sentences into terms and map them by index
Map<Integer, Set<String>> sentencesSplit = new HashMap<>();
for (int j = 0; j < sentences.size(); j++) {
String[] splitSentence = sentences.get(j).split(" ");
Set<String> sentenceSet = new HashSet<>();
sentencesSplit.put(j, sentenceSet);
for (int i = 0; i < splitSentence.length; i++) {
sentenceSet.add(splitSentence[i]);
}
}
// Split the query into terms and map them by index
Map<Integer, String[]> queriesSplit = new HashMap<>();
for (int i = 0; i < queries.size(); i++) {
queriesSplit.put(i, queries.get(i).split(" "));
}
for (int i = 0; i < queries.size(); i++) {
String found = null;
for (int j = 0; j < sentences.size(); j++) {
String[] splitQuery = queriesSplit.get(i);
Set<String> sentenceStringList = sentencesSplit.get(j);
boolean notFound = false;
for (int k = 0; k < splitQuery.length; k++) {
if (!sentenceStringList.contains(splitQuery[k])) {
notFound = true;
break;
}
}
if (!notFound) {
if (found == null) {
found = "" + j;
} else {
found += " " + j;
}
}
}
if (found == null) {
found = "-1";
}
System.out.println(found);
}
}
最佳答案
我的代码和人类的思维很相似。
\b 允许您使用\bword\b 形式的正则表达式执行“仅整个单词”搜索。
希望我的代码能帮到你。
public class MainClass {
public static void main(String [] args)
{
List<String> sentences = new ArrayList<String>();
sentences.add("Pulkit likes StackOverflow and coding");
sentences.add("Pulkit does not like Reddit");
sentences.add("Pulkit like ice cream");
List<String> queries = new ArrayList<String>();
queries.add("Pulkit coding");
queries.add("like");
queries.add("does");
findMatch(sentences, queries);
}
public static void findMatch(List<String> sentences, List<String> queries) {
for(String query : queries) {
System.out.print("]");
String match = ".*\\b" + query.replace(" ", "\\b.*") + "\\b.*";
for (int iSentence = 0; iSentence < sentences.size(); iSentence++) {
if(sentences.get(iSentence).matches(match)) {
System.out.print(" " + iSentence);
}
}
System.out.println("");
}
}
}
控制台输出:
] 0
] 1 2
] 1
关于java - 给定两个列表,查找字符串中子字符串的出现次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52980518/