найти вхождение подстрок в строку по заданному списку

Question

С учетом двух предложений списка и запросов списка

У меня есть два запроса о нахождении запросов в предложениях.

Пример,

1. "Пулькит лайков"StackOverflow и кодирование "

2. " Пулькит не любит 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