java - 给定两个列表，查找字符串中子字符串的出现次数

Question

给定两个列表句子和列表查询

我有两个查找句子中查询出现的情况。

示例，

1. “Pulkit 喜欢 StackOverflow 和编码”

2. “Pulkit 不喜欢 Reddit”

3. “像冰淇淋一样的果肉”

查询

1. Pulkit 编码

2. 喜欢

3. 是

该函数应返回查询

1. 句子[0]

2. 句子[1]、句子[2]

3. 句子[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);
        }
    }

Answer 1

我的代码和人类的思维很相似。

\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